1 /*
2 Numdiff - compare putatively similar files,
3 ignoring small numeric differences
4 Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017 Ivano Primi <ivprimi@libero.it>
5
6 This program is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include <stdio.h>
21 #include <stdlib.h>
22 #include <string.h>
23 #include "bitvector.h"
24
25 static
exitOnOutOfMemory(int lineNo,size_t nBytes)26 void exitOnOutOfMemory (int lineNo, size_t nBytes)
27 {
28 fprintf (stderr,
29 "*** Out of memory occurred at line %d of file %s\n"
30 "*** while trying to allocate space for %zu bytes,\n"
31 "*** exit now!\n",
32 lineNo, __FILE__, nBytes);
33 exit (EXIT_FAILURE);
34 }
35
36 static
arrangeMemoryFor(bitvector * bv,size_t newSize)37 size_t arrangeMemoryFor (bitvector* bv, size_t newSize)
38 {
39 if (!bv || newSize == 0)
40 return 0;
41 else
42 {
43 /*
44 BV is not the null pointer and
45 NEWSIZE is greater than zero.
46 */
47 if (!(bv->ptr))
48 {
49 bv->ptr = (byte_t*) calloc (newSize, sizeof(byte_t));
50 bv->sz = (!bv->ptr ? 0 : newSize);
51 }
52 else
53 {
54 /* BV->PTR is not the null pointer */
55 if (newSize != bv->sz)
56 {
57 byte_t* tmp = (byte_t*) realloc (bv->ptr, newSize * sizeof(byte_t));
58 if (!tmp)
59 {
60 return 0;
61 }
62 else
63 {
64 bv->ptr = tmp;
65 if (newSize > bv->sz)
66 {
67 memset (bv->ptr + bv->sz * sizeof(byte_t), 0, (newSize-bv->sz) * sizeof(byte_t));
68 }
69 bv->sz = newSize;
70 }
71 }
72 }
73 return bv->sz;
74 }
75 }
76
77 static
getBitFrom(byte_t * barray,size_t pos)78 int getBitFrom (byte_t* barray, size_t pos)
79 {
80 return ( (barray[pos / NBITS_PER_BYTE] & (0x1 << pos % NBITS_PER_BYTE)) == 0
81 ? BIT_OFF : BIT_ON );
82 }
83
84 static
setBit(byte_t * barray,size_t pos,int value)85 void setBit (byte_t* barray, size_t pos, int value)
86 {
87 if (value == BIT_OFF)
88 barray[pos / NBITS_PER_BYTE] &= ~(0x1 << pos % NBITS_PER_BYTE);
89 else
90 barray[pos / NBITS_PER_BYTE] |= (0x1 << pos % NBITS_PER_BYTE);
91 }
92
93 static
flipBit(byte_t * barray,size_t pos)94 void flipBit (byte_t* barray, size_t pos)
95 {
96 barray[pos / NBITS_PER_BYTE] ^= (0x1 << pos % NBITS_PER_BYTE);
97 }
98
newBitVector(size_t requestedSize)99 bitvector newBitVector (size_t requestedSize)
100 {
101 bitvector bv = {(byte_t*)0, 0};
102 size_t sizeInBytes = (requestedSize > 0 ? (requestedSize - 1) / NBITS_PER_BYTE + 1 : 0);
103
104 if ( arrangeMemoryFor (&bv, sizeInBytes) < sizeInBytes )
105 {
106 exitOnOutOfMemory (__LINE__, sizeInBytes * sizeof(byte_t));
107 }
108 return bv;
109 }
110
getBitVectorSize(const bitvector * bv)111 size_t getBitVectorSize (const bitvector* bv)
112 {
113 return ((bv) ? NBITS_PER_BYTE * bv->sz : (size_t)(-1));
114 }
115
getBitAtPosition(const bitvector * bv,size_t pos)116 int getBitAtPosition (const bitvector* bv, size_t pos)
117 {
118 if (!bv || !bv->ptr || pos >= bv->sz * NBITS_PER_BYTE)
119 {
120 return BIT_ERR;
121 }
122 else
123 {
124 return getBitFrom (bv->ptr, pos);
125 }
126 }
127
getBitsInRange(const bitvector * bv,size_t startpos,size_t endpos)128 int* getBitsInRange (const bitvector* bv, size_t startpos, size_t endpos)
129 {
130 if (!bv || !bv->ptr)
131 {
132 return (int*)0;
133 }
134 else
135 {
136 const size_t szInBits = bv->sz * NBITS_PER_BYTE;
137
138 if (endpos <= startpos || startpos >= szInBits)
139 {
140 return (int*)0;
141 }
142 else
143 {
144 /* 0 <= STARTPOS < ENDPOS, and STARTPOS < SZINBITS */
145 const size_t difference = endpos - startpos;
146 size_t idx;
147 int* barray = (int*) malloc (difference*sizeof(int));
148
149 if (!barray)
150 {
151 exitOnOutOfMemory (__LINE__, difference*sizeof(int));
152 }
153 for (idx = startpos; idx < szInBits; idx++)
154 {
155 barray[idx-startpos] = getBitFrom (bv->ptr, idx);
156 }
157 for (idx -= startpos; idx < difference; barray[idx++] = BIT_ERR);
158 return barray;
159 }
160 }
161 }
162
setBitAtPosition(bitvector * bv,size_t pos,int value)163 void setBitAtPosition (bitvector* bv, size_t pos, int value)
164 {
165 if ((bv))
166 {
167 if (pos >= bv->sz * NBITS_PER_BYTE)
168 {
169 if ( arrangeMemoryFor (bv, pos / NBITS_PER_BYTE + 1) == 0 )
170 {
171 exitOnOutOfMemory (__LINE__, (pos / NBITS_PER_BYTE + 1)*sizeof(byte_t));
172 }
173 }
174 /* Whenever we arrive here POS < BV->SZ * NBITS_PER_BYTE */
175 setBit (bv->ptr, pos, value);
176 }
177 }
178
setBitsInRange(bitvector * bv,size_t startpos,size_t endpos,const int * varray)179 void setBitsInRange (bitvector* bv, size_t startpos, size_t endpos, const int* varray)
180 {
181 if ((bv))
182 {
183 if (endpos > startpos && endpos > bv->sz * NBITS_PER_BYTE)
184 {
185 if ( arrangeMemoryFor (bv, (endpos-1) / NBITS_PER_BYTE + 1) == 0 )
186 {
187 exitOnOutOfMemory (__LINE__, ((endpos-1) / NBITS_PER_BYTE + 1)*sizeof(byte_t));
188 }
189 }
190 size_t pos;
191
192 for (pos = startpos; pos < endpos; pos++)
193 {
194 setBit (bv->ptr, pos, varray[pos-startpos]);
195 }
196 }
197 }
198
setBitsInRangeToValue(bitvector * bv,size_t startpos,size_t endpos,int value)199 void setBitsInRangeToValue (bitvector* bv, size_t startpos, size_t endpos, int value)
200 {
201 if ((bv))
202 {
203 size_t effectiveEnd = endpos;
204
205 if (endpos > startpos && endpos > bv->sz * NBITS_PER_BYTE)
206 {
207 if ( arrangeMemoryFor (bv, (endpos-1) / NBITS_PER_BYTE + 1) == 0 )
208 {
209 exitOnOutOfMemory (__LINE__, ((endpos-1) / NBITS_PER_BYTE + 1)*sizeof(byte_t));
210 }
211 if (value == 0)
212 effectiveEnd = bv->sz * NBITS_PER_BYTE;
213 }
214 size_t pos;
215
216 for (pos = startpos; pos < effectiveEnd; pos++)
217 {
218 setBit (bv->ptr, pos, value);
219 }
220 }
221 }
222
flipBitsInRange(bitvector * bv,size_t startpos,size_t endpos)223 size_t flipBitsInRange (bitvector* bv, size_t startpos, size_t endpos)
224 {
225 if ((bv) && (bv->ptr) && bv->sz > 0)
226 {
227 size_t pos, afterlast = bv->sz * NBITS_PER_BYTE;
228 size_t lbd = startpos / NBITS_PER_BYTE + 1;
229 size_t ubd;
230
231 if (endpos < afterlast)
232 {
233 afterlast = endpos;
234 }
235 ubd = afterlast / NBITS_PER_BYTE;
236
237 if (lbd <= ubd)
238 {
239 for (pos = lbd; pos < ubd; pos++)
240 {
241 bv->ptr[pos] = ~(bv->ptr[pos]);
242 }
243 lbd *= NBITS_PER_BYTE;
244 for (pos = startpos; pos < lbd; pos++)
245 {
246 flipBit (bv->ptr, pos);
247 }
248 ubd *= NBITS_PER_BYTE;
249 for (pos = ubd; pos < afterlast; pos++)
250 {
251 flipBit (bv->ptr, pos);
252 }
253 }
254 else
255 {
256 for (pos = startpos; pos < afterlast; pos++)
257 {
258 flipBit (bv->ptr, pos);
259 }
260 }
261 return (startpos < afterlast ? afterlast - startpos : 0);
262 }
263 else
264 {
265 return 0;
266 }
267 }
268
printBitVectorOn(const bitvector * bv,FILE * fp)269 size_t printBitVectorOn (const bitvector* bv, FILE* fp)
270 {
271 if ((bv) && (bv->ptr) && bv->sz > 0)
272 {
273 const size_t szInBits = bv->sz * NBITS_PER_BYTE;
274 size_t pos, idx = 0;
275 int bitValue, rv = ' ';
276
277 do
278 {
279 pos = szInBits - (++idx);
280 bitValue = getBitFrom (bv->ptr, pos);
281 rv = putc ((bitValue == BIT_OFF ? '0' : '1'), fp);
282 } while (idx < szInBits && rv != EOF);
283 return (rv != EOF ? szInBits : idx-1);
284 }
285 else
286 {
287 return 0;
288 }
289 }
290
emptyBitVector(bitvector * bv)291 void emptyBitVector (bitvector* bv)
292 {
293 if ((bv) && (bv->ptr))
294 {
295 free ((void*)bv->ptr);
296 bv->ptr = (byte_t*)0;
297 bv->sz = 0;
298 }
299 }
300