1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
2 * Copyright by The HDF Group. *
3 * Copyright by the Board of Trustees of the University of Illinois. *
4 * All rights reserved. *
5 * *
6 * This file is part of HDF. The full HDF copyright notice, including *
7 * terms governing use, modification, and redistribution, is contained in *
8 * the COPYING file, which can be found at the root of the source code *
9 * distribution tree, or in https://support.hdfgroup.org/ftp/HDF/releases/. *
10 * If you do not have access to either file, you may request a copy from *
11 * help@hdfgroup.org. *
12 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
13
14 /* $Id$ */
15
16 /*
17 FILE
18 bitvect.c
19
20 PURPOSE
21 Provide an API for dynamicly-sized bit-vectors or "bit-sets"
22
23 REMARKS
24 These function manipulate ordered sets of "bits". They are designed
25 to closely resemble the functions which one can perform in C with the
26 "bit-wise" algebraic functions, with some additional pizzaz thrown in.
27
28 DESIGN
29 These routines a designed to be a modular component for use both
30 inside the HDF library and out.
31 They will use the HDF typedefs & Standard C library macros, but do
32 not explicitly depend on being inside the library itself.
33 Each bit-vector is stored in memory as an array of unsigned 8-bit
34 integers (uint8's in HDF types), which can grow as additional bits are
35 flagged in the bit-vector.
36 Each bit-vector is stored with the lowest bits in location 0 in the
37 array of base type (uint8s currently) and the bits in "standard" C order
38 (i.e. bit 0 is the lowest bit in the byte) in each byte. This does make
39 for a slightly strange "bit-swapped" storage, but is the most efficient.
40
41 BUGS/LIMITATIONS
42 Currently the following design limitations are still in place:
43
44 EXPORTED ROUTINES
45
46 bv_ptr bv_new(int32 num_bits, uint32 flags)
47 - Creates a new bit-vector with a particular starting # of bits.
48
49 intn bv_delete(bv_ptr b)
50 - Deletes a bit-vector created with bv_new.
51
52 intn bv_set(bv_ptr b, int32 bit_num, bv_bool value)
53 - Sets a bit in a bit-vector to a given boolean value.
54
55 intn bv_get(bv_ptr b, int32 bit_num)
56 - Gets a bit from a bit-vector.
57
58 intn bv_clear(bv_ptr b, bv_bool value)
59 - Clears an entire bit-vector to a given boolean value.
60
61 int32 bv_size(bv_ptr b)
62 - Reports the number of bits used in a bit-vector.
63
64 uint32 bv_flags(bv_ptr b)
65 - Returns the flags used when creating the bit-vector
66
67 int32 bv_find(bv_ptr b, int32 last_find, bv_bool value)
68 - Find the next bit in a bit-vector with a given value.
69
70 Functions that it would be nice to see (some day):
71
72 intn bv_bitand(bv_ptr b, int32 bit_num, bv_bool value)
73 - Perform a boolean AND operation on a bit in a bit-vector.
74
75 intn bv_bitor(bv_ptr b, int32 bit_num, bv_bool value)
76 - Perform a boolean OR operation on a bit in a bit-vector.
77
78 intn bv_bitxor(bv_ptr b, int32 bit_num, bv_bool value)
79 - Perform a boolean XOR operation on a bit in a bit-vector.
80
81 intn bv_bitnot(bv_ptr b, int32 bit_num)
82 - Perform a boolean NOT operation on a bit in a bit-vector.
83
84 bv_ptr *bv_vectand(bv_ptr b1, bv_ptr b2)
85 - Perform a boolean AND operation between two bit-vectors.
86
87 bv_ptr *bv_vector(bv_ptr b1, bv_ptr b2)
88 - Perform a boolean OR operation between two bit-vectors.
89
90 bv_ptr *bv_vectxor(bv_ptr b1, bv_ptr b2)
91 - Perform a boolean XOR operation between two bit-vectors.
92
93 LOCAL ROUTINES
94
95 AUTHOR
96 Quincey Koziol
97
98 MODIFICATION HISTORY
99 12/05/95 - Starting writing specs & coding prototype
100 */
101
102 #define BV_MASTER
103 #include "bitvect.h" /* Multi-file raster information */
104
105 /* Local pre-processor macros */
106
107 /*--------------------------------------------------------------------------
108 NAME
109 bv_new
110 PURPOSE
111 Create a new bit-vector.
112 USAGE
113 bv_ptr bv_new(num_bits, flags)
114 int32 num_bits; IN: The initial number of bits in the vector
115 uint32 flags; IN: Flags to determine special attributes
116 of the newly created bit-vector
117 RETURNS
118 Returns either a valid bv_ptr on succeed or NULL on failure.
119 DESCRIPTION
120 Creates a new bit-vector with a certain initial # of bits.
121 GLOBAL VARIABLES
122 COMMENTS, BUGS, ASSUMPTIONS
123 If num_bits is set to (-1), then the default number of bits is used.
124 EXAMPLES
125 REVISION LOG
126 --------------------------------------------------------------------------*/
bv_new(int32 num_bits,uint32 flags)127 bv_ptr bv_new(int32 num_bits, uint32 flags)
128 {
129 int32 base_elements; /* the number of base elements needed to store the # of bits requested */
130 bv_ptr b; /* ptr to the new bit-vector */
131
132 /* Check for invalid numbers of bits or bad flags */
133 if(num_bits<(-1) || num_bits==0)
134 return(NULL);
135
136 /* Check for requesting the default # of bits */
137 if(num_bits==(-1))
138 num_bits=BV_DEFAULT_BITS;
139
140 base_elements=((num_bits%(int32)BV_BASE_BITS)>0) ? (num_bits/(int32)BV_BASE_BITS)+1 : (num_bits/(int32)BV_BASE_BITS);
141
142 if((b=(bv_ptr)HDmalloc(sizeof(bv_struct)))==NULL)
143 return(NULL);
144
145 b->bits_used=(uint32)num_bits;
146 b->array_size=(uint32)(((base_elements/BV_CHUNK_SIZE)+1)*BV_CHUNK_SIZE);
147 b->flags=flags;
148 if((b->buffer=(bv_base *)HDmalloc(sizeof(bv_base)*b->array_size))==NULL)
149 {
150 HDfree(b);
151 return(NULL);
152 } /* end if */
153
154 /* Check the initial bit settings */
155 if(flags&BV_INIT_TO_ONE)
156 {
157 HDmemset(b->buffer,255,b->array_size);
158 b->last_zero=(-1); /* Set the last zero to unknown */
159 } /* end if */
160 else
161 {
162 HDmemset(b->buffer,0,b->array_size);
163 b->last_zero=0;
164 } /* end else */
165
166 return(b);
167 } /* bv_new() */
168
169 /*--------------------------------------------------------------------------
170 NAME
171 bv_delete
172 PURPOSE
173 Dispose of a new bit-vector.
174 USAGE
175 intn bv_delete(b)
176 bv_ptr b; IN: Bit-vector to dispose of
177 RETURNS
178 Returns SUCCEED/FAIL
179 DESCRIPTION
180 Disposes of a bit-vector created by bv_new. This routine is responsible
181 for completely cleaning up the bit-vector and disposing of all dynamicly
182 allocated space.
183 GLOBAL VARIABLES
184 COMMENTS, BUGS, ASSUMPTIONS
185 EXAMPLES
186 REVISION LOG
187 --------------------------------------------------------------------------*/
bv_delete(bv_ptr b)188 intn bv_delete(bv_ptr b)
189 {
190 /* Error checking */
191 if(b==NULL || b->buffer==NULL)
192 return(FAIL);
193
194 /* Free the space used */
195 HDfree(b->buffer);
196 HDfree(b);
197
198 return(SUCCEED);
199 } /* bv_delete() */
200
201 /*--------------------------------------------------------------------------
202 NAME
203 bv_set
204 PURPOSE
205 Set a bit in a bit-vector
206 USAGE
207 intn bv_set(b,bit_num,value)
208 bv_ptr b; IN: Bit-vector to use
209 int32 bit_num; IN: bit to set
210 bv_bool value; IN: bit value to set the bit to
211 RETURNS
212 Returns SUCCEED/FAIL
213 DESCRIPTION
214 Sets a bit in a bit-vector to a bit value. Also extends the bit-vector
215 if the bit to set is beyond the end of the current bit-vector and the
216 bit-vector is marked as extendable.
217 GLOBAL VARIABLES
218 COMMENTS, BUGS, ASSUMPTIONS
219 EXAMPLES
220 REVISION LOG
221 --------------------------------------------------------------------------*/
bv_set(bv_ptr b,int32 bit_num,bv_bool value)222 intn bv_set(bv_ptr b, int32 bit_num, bv_bool value)
223 {
224 int32 base_elem; /* the base array index of the bit */
225 int32 bit_elem; /* the bit index of the bit to set */
226
227 /* Error checking */
228 if(b==NULL || bit_num<0)
229 return(FAIL);
230
231 base_elem=bit_num/(int32)BV_BASE_BITS;
232 bit_elem=bit_num%(int32)BV_BASE_BITS;
233
234 /* Check if the bit is beyond the end of the current bit-vector */
235 if((uint32)bit_num>=b->bits_used)
236 {
237 /* OK to extend? */
238 if(b->flags&BV_EXTENDABLE)
239 {
240 if((uint32)base_elem<b->array_size)
241 { /* just use more bits in the currently allocated block */
242 b->bits_used=(uint32)(bit_num+1);
243 } /* end if */
244 else
245 { /* allocate more space for bits */
246 bv_base *old_buf=b->buffer; /* ptr to the old buffer */
247 int32 num_chunks; /* number of chunks to grab */
248
249 num_chunks=(int32)(((((uint32)bit_num/BV_BASE_BITS)+1)-b->array_size)/BV_CHUNK_SIZE)+1;
250 if((b->buffer=(bv_base *)HDrealloc(b->buffer,b->array_size+(uint32)num_chunks*BV_CHUNK_SIZE))==NULL)
251 {
252 b->buffer=old_buf;
253 return(FAIL); /* fail to allocate a larger bit buffer */
254 } /* end if */
255
256 /* Check the initial bit settings, for the new bits */
257 if(b->flags&BV_INIT_TO_ONE)
258 HDmemset(&b->buffer[b->array_size],255,num_chunks*BV_CHUNK_SIZE);
259 else
260 HDmemset(&b->buffer[b->array_size],0,num_chunks*BV_CHUNK_SIZE);
261
262 b->array_size+=(uint32)(num_chunks*BV_CHUNK_SIZE);
263 b->bits_used=(uint32)bit_num+1;
264 } /* end else */
265 } /* end if */
266 else
267 return(FAIL); /* can't extend */
268 } /* end if */
269
270 if(value==BV_FALSE)
271 {
272 b->buffer[base_elem]&=~bv_bit_value[bit_elem];
273 if(base_elem<b->last_zero)
274 b->last_zero=base_elem;
275 } /* end if */
276 else
277 b->buffer[base_elem]|=bv_bit_value[bit_elem];
278
279 return(SUCCEED);
280 } /* bv_set() */
281
282 /*--------------------------------------------------------------------------
283 NAME
284 bv_get
285 PURPOSE
286 Get a bit from a bit-vector
287 USAGE
288 intn bv_get(b,bit_num)
289 bv_ptr b; IN: Bit-vector to use
290 int32 bit_num; IN: bit to set
291 RETURNS
292 Returns either BV_TRUE/BV_FALSE on success, or FAIL on error
293 DESCRIPTION
294 Gets a bit from a bit-vector.
295 GLOBAL VARIABLES
296 COMMENTS, BUGS, ASSUMPTIONS
297 EXAMPLES
298 REVISION LOG
299 --------------------------------------------------------------------------*/
bv_get(bv_ptr b,int32 bit_num)300 intn bv_get(bv_ptr b, int32 bit_num)
301 {
302 int32 base_elem; /* the base array index of the bit */
303 int32 bit_elem; /* the bit index of the bit to set */
304 intn ret_value; /* the variable to store the return value */
305
306 /* Error checking */
307 if(b==NULL || b->buffer==NULL || bit_num<0)
308 return(FAIL);
309
310 /* Check for asking for a bit off of the end of the vector */
311 if((uint32)bit_num>=b->bits_used)
312 return((b->flags&BV_INIT_TO_ONE) ? BV_TRUE : BV_FALSE);
313
314 base_elem=bit_num/(int32)BV_BASE_BITS;
315 bit_elem=bit_num%(int32)BV_BASE_BITS;
316
317 ret_value=b->buffer[base_elem]&bv_bit_value[bit_elem];
318 ret_value>>=bit_elem;
319
320 return(ret_value);
321 } /* bv_get() */
322
323 /*--------------------------------------------------------------------------
324 NAME
325 bv_clear
326 PURPOSE
327 Clears a bit-vector to a given boolean value
328 USAGE
329 intn bv_clear(b,value)
330 bv_ptr b; IN: Bit-vector to use
331 bv_bool value; IN: bit value to set the bit to
332 RETURNS
333 Returns SUCCEED/FAIL
334 DESCRIPTION
335 Clears an entire bit vector to a given boolean value, but does not
336 change the status of the BV_INIT_TO_ONE flag for future bits which
337 might be allocated.
338 GLOBAL VARIABLES
339 COMMENTS, BUGS, ASSUMPTIONS
340 EXAMPLES
341 REVISION LOG
342 --------------------------------------------------------------------------*/
bv_clear(bv_ptr b,bv_bool value)343 intn bv_clear(bv_ptr b, bv_bool value)
344 {
345 /* Error checking */
346 if(b==NULL || b->buffer==NULL)
347 return(FAIL);
348
349 if(value==BV_TRUE)
350 {
351 HDmemset(b->buffer,255,b->array_size);
352 b->last_zero=(-1);
353 } /* end if */
354 else
355 {
356 HDmemset(b->buffer,0,b->array_size);
357 b->last_zero=0;
358 } /* end else */
359
360 return(SUCCEED);
361 } /* bv_clear() */
362
363 /*--------------------------------------------------------------------------
364 NAME
365 bv_size
366 PURPOSE
367 Report the number of bits in the bit-vector
368 USAGE
369 int32 bv_size(b)
370 bv_ptr b; IN: Bit-vector to use
371 RETURNS
372 Returns number of bits in use on success, FAIL on error
373 DESCRIPTION
374 Report the number of bits currently in-use for a bit-vector.
375 GLOBAL VARIABLES
376 COMMENTS, BUGS, ASSUMPTIONS
377 EXAMPLES
378 REVISION LOG
379 --------------------------------------------------------------------------*/
bv_size(bv_ptr b)380 int32 bv_size(bv_ptr b)
381 {
382 /* Error checking */
383 if(b==NULL)
384 return(FAIL);
385
386 return((int32)b->bits_used);
387 } /* bv_size() */
388
389 /*--------------------------------------------------------------------------
390 NAME
391 bv_flags
392 PURPOSE
393 Returns the flags for a bit-vector
394 USAGE
395 uint32 bv_size(b)
396 bv_ptr b; IN: Bit-vector to use
397 RETURNS
398 Returns bit-vector flags on success, FAIL on error
399 DESCRIPTION
400 Returns the current flags for the bit-vector.
401 GLOBAL VARIABLES
402 COMMENTS, BUGS, ASSUMPTIONS
403 EXAMPLES
404 REVISION LOG
405 --------------------------------------------------------------------------*/
bv_flags(bv_ptr b)406 uint32 bv_flags(bv_ptr b)
407 {
408 /* Error checking */
409 if(b==NULL)
410 return(FAIL);
411
412 return(b->flags);
413 } /* bv_flags() */
414
415 /*--------------------------------------------------------------------------
416 NAME
417 bv_find
418 PURPOSE
419 Find the next bit of a given value
420 USAGE
421 int32 bv_find(b,last_find,value)
422 bv_ptr b; IN: Bit-vector to use
423 int32 last_find; IN: bit offset of last bit found
424 bv_bool value; IN: boolean value to look for
425 RETURNS
426 Returns offset of next bit on success, FAIL on error
427 DESCRIPTION
428 Find the next highest bit of a given bit value.
429 GLOBAL VARIABLES
430 COMMENTS, BUGS, ASSUMPTIONS
431 "last_find" capability not currently implemented for '0' searches - QAK
432 EXAMPLES
433 REVISION LOG
434 --------------------------------------------------------------------------*/
bv_find(bv_ptr b,int32 last_find,bv_bool value)435 int32 bv_find(bv_ptr b,int32 last_find,bv_bool value)
436 {
437 uint32 old_bits_used; /* the last number of bits used */
438 uint32 bytes_used; /* number of full bytes used */
439 uint32 first_byte=0; /* The first byte to begin searching at */
440 bv_base slush_bits; /* extra bits which don't fit into a byte */
441 uint32 u; /* local counting variable */
442
443 /* Error checking */
444 if(b==NULL || b->buffer==NULL)
445 return(FAIL);
446
447 bytes_used=b->bits_used/BV_BASE_BITS;
448 if(value==BV_TRUE)
449 { /* looking for first '1' in the bit-vector */
450 if(last_find>=0)
451 { /* if the last bit found option is used, look for more bits in that same byte */
452 intn bit_off;
453 int unused;
454
455 first_byte=(uint32)last_find/BV_BASE_BITS;
456 bit_off=(intn)(((uint32)last_find-(first_byte*BV_BASE_BITS))+1);
457 slush_bits=(bv_base)(b->buffer[first_byte]&(~bv_bit_mask[bit_off]));
458 if(slush_bits!=0)
459 return((int32)(first_byte*BV_BASE_BITS)+bv_first_zero[(~slush_bits)]);
460 /* return((int32)(first_byte*BV_BASE_BITS)+bv_first_zero[(bv_base)(~slush_bits)]);
461 */
462 first_byte++;
463 } /* end if */
464
465 for(u=first_byte; u<bytes_used; u++)
466 {
467 if(b->buffer[u]!=0)
468 return((int32)(u*BV_BASE_BITS)+bv_first_zero[~b->buffer[u]]);
469 } /* end for */
470
471 /* Any extra bits left over? */
472 if((bytes_used*BV_BASE_BITS)<b->bits_used)
473 {
474 slush_bits=(bv_base)(b->buffer[u]&bv_bit_mask[b->bits_used-(bytes_used*BV_BASE_BITS)]);
475 if(slush_bits!=0)
476 return((int32)(u*BV_BASE_BITS)+bv_first_zero[(bv_base)(~slush_bits)]);
477 } /* end if */
478 } /* end if */
479 else
480 { /* looking for first '0' in the bit-vector */
481 bv_base *tmp_buf;
482
483 if(b->last_zero>=0)
484 u=(uint32)b->last_zero;
485 else
486 u=0;
487 #ifdef OLD_WAY
488 for(; u<bytes_used; u++)
489 {
490 if(b->buffer[u]!=255)
491 {
492 b->last_zero=u;
493 return((u*BV_BASE_BITS)+bv_first_zero[b->buffer[u]]);
494 } /* end if */
495 } /* end for */
496 #else /* OLD_WAY */
497 tmp_buf=&b->buffer[u];
498 while(u<bytes_used && *tmp_buf==255)
499 {
500 u++;
501 tmp_buf++;
502 } /* end while */
503 if(u<bytes_used)
504 {
505 b->last_zero=(int32)u;
506 return((int32)(u*BV_BASE_BITS)+bv_first_zero[*tmp_buf]);
507 } /* end if */
508 #endif /* OLD_WAY */
509
510 /* Any extra bits left over? */
511 if((bytes_used*BV_BASE_BITS)<b->bits_used)
512 {
513 slush_bits=(bv_base)(b->buffer[u]&bv_bit_mask[b->bits_used-(bytes_used*BV_BASE_BITS)]);
514 if(slush_bits!=255)
515 {
516 b->last_zero=(int32)u;
517 return((int32)(u*BV_BASE_BITS)+bv_first_zero[slush_bits]);
518 } /* end if */
519 } /* end if */
520 } /* end else */
521
522 /* Beyond the current end of the bit-vector, extend the bit-vector */
523 old_bits_used=b->bits_used;
524 if(bv_set(b, (int32)b->bits_used, (bv_bool)((b->flags&BV_INIT_TO_ONE) ? BV_TRUE : BV_FALSE))==FAIL)
525 return(FAIL);
526
527 return((int32)old_bits_used);
528 } /* bv_find() */
529
530