1 /******************************************************************************
2 * $Id$
3 *
4 * Project: MapServer
5 * Purpose: Implementation of bit array functions.
6 * Author: Steve Lime and the MapServer team.
7 *
8 * Notes: Derived from code placed in the public domain by Bob Stout, for more
9 * information see http://c.snippets.org/snip_lister.php?fname=bitarray.c.
10 *
11 ******************************************************************************
12 * Copyright (c) 1996-2005 Regents of the University of Minnesota.
13
14 * Permission is hereby granted, free of charge, to any person obtaining a
15 * copy of this software and associated documentation files (the "Software"),
16 * to deal in the Software without restriction, including without limitation
17 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
18 * and/or sell copies of the Software, and to permit persons to whom the
19 * Software is furnished to do so, subject to the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be included in
22 * all copies of this Software or works derived from this Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
25 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
26 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
27 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
28 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
29 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
30 * DEALINGS IN THE SOFTWARE.
31 ****************************************************************************/
32
33 #include "mapserver.h"
34
35
36
37 #include <limits.h>
38
39 /*
40 * Hardcoded size of our bit array.
41 * See function msGetNextBit for another hardcoded value.
42 */
43
44 /* #define msGetBit(array, index) (*((array) + (index)/MS_ARRAY_BIT) & ( 1 << ((index) % MS_ARRAY_BIT))) */
45
msGetBitArraySize(int numbits)46 size_t msGetBitArraySize(int numbits)
47 {
48 return((numbits + MS_ARRAY_BIT - 1) / MS_ARRAY_BIT);
49 }
50
msAllocBitArray(int numbits)51 ms_bitarray msAllocBitArray(int numbits)
52 {
53 ms_bitarray array = calloc((numbits + MS_ARRAY_BIT - 1) / MS_ARRAY_BIT, MS_ARRAY_BIT);
54
55 return(array);
56 }
57
msGetBit(ms_const_bitarray array,int index)58 int msGetBit(ms_const_bitarray array, int index)
59 {
60 array += index / MS_ARRAY_BIT;
61 return (*array & (1 << (index % MS_ARRAY_BIT))) != 0; /* 0 or 1 */
62 }
63
64 /*
65 ** msGetNextBit( status, start, size)
66 **
67 ** Quickly find the next bit set. If start == 0 and 0 is set, will return 0.
68 ** If hits end of bitmap without finding set bit, will return -1.
69 **
70 */
msGetNextBit(ms_const_bitarray array,int i,int size)71 int msGetNextBit(ms_const_bitarray array, int i, int size)
72 {
73
74 register ms_uint32 b;
75
76 while(i < size) {
77 b = *(array + (i/MS_ARRAY_BIT));
78 if( b && (b >> (i % MS_ARRAY_BIT)) ) {
79 /* There is something in this byte */
80 /* And it is not to the right of us */
81 if( b & ( 1 << (i % MS_ARRAY_BIT)) ) {
82 /* There is something at this bit! */
83 return i;
84 } else {
85 i++;
86 }
87 } else {
88 /* Nothing in this byte, move to start of next byte */
89 i += MS_ARRAY_BIT - (i % MS_ARRAY_BIT);
90 }
91 }
92
93 /* Got to the last byte with no hits! */
94 return -1;
95 }
96
msSetBit(ms_bitarray array,int index,int value)97 void msSetBit(ms_bitarray array, int index, int value)
98 {
99 array += index / MS_ARRAY_BIT;
100 if (value)
101 *array |= 1 << (index % MS_ARRAY_BIT); /* set bit */
102 else
103 *array &= ~(1 << (index % MS_ARRAY_BIT)); /* clear bit */
104 }
105
msSetAllBits(ms_bitarray array,int numbits,int value)106 void msSetAllBits(ms_bitarray array, int numbits, int value)
107 {
108 if (value)
109 memset(array, 0xff, ((numbits + 7) / 8) ); /* set bit */
110 else
111 memset(array, 0x0, ((numbits + 7) / 8) ); /* clear bit */
112 }
113
msFlipBit(ms_bitarray array,int index)114 void msFlipBit(ms_bitarray array, int index)
115 {
116 array += index / MS_ARRAY_BIT;
117 *array ^= 1 << (index % MS_ARRAY_BIT); /* flip bit */
118 }
119