source: trunk/libtransmission/bitfield.c @ 14526

Last change on this file since 14526 was 14526, checked in by mikedld, 6 years ago

Fix some issues revealed by coverity

  • Property svn:keywords set to Date Rev Author Id
File size: 9.4 KB
Line 
1/*
2 * This file Copyright (C) 2008-2014 Mnemosyne LLC
3 *
4 * It may be used under the GNU GPL versions 2 or 3
5 * or any future license endorsed by Mnemosyne LLC.
6 *
7 * $Id: bitfield.c 14526 2015-05-09 11:56:35Z mikedld $
8 */
9
10#include <assert.h>
11#include <stdlib.h> /* realloc () */
12#include <string.h> /* memset */
13
14#include "transmission.h"
15#include "bitfield.h"
16#include "utils.h" /* tr_new0 () */
17
18const tr_bitfield TR_BITFIELD_INIT = { NULL, 0, 0, 0, false, false };
19
20/****
21*****
22****/
23
24static const int8_t trueBitCount[256] =
25{
26  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
27  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
28  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
29  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
30  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
31  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
32  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
33  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
34  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
35  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
36  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
37  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
38  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
39  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
40  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
41  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
42};
43
44static size_t
45countArray (const tr_bitfield * b)
46{
47  size_t ret = 0;
48  size_t i = b->alloc_count;
49
50  while (i > 0)
51    ret += trueBitCount[b->bits[--i]];
52
53  return ret;
54}
55
56static size_t
57countRange (const tr_bitfield * b, size_t begin, size_t end)
58{
59  size_t ret = 0;
60  const size_t first_byte = begin >> 3u;
61  const size_t last_byte = (end - 1) >> 3u;
62
63  if (!b->bit_count)
64    return 0;
65
66  if (first_byte >= b->alloc_count)
67    return 0;
68
69  assert (begin < end);
70  assert (b->bits != NULL);
71
72  if (first_byte == last_byte)
73    {
74      int i;
75      uint8_t val = b->bits[first_byte];
76
77      i = begin - (first_byte * 8);
78      val <<= i;
79      val >>= i;
80      i = (last_byte+1)*8 - end;
81      val >>= i;
82      val <<= i;
83
84      ret += trueBitCount[val];
85    }
86  else
87    {
88      size_t i;
89      uint8_t val;
90      const size_t walk_end = MIN (b->alloc_count, last_byte);
91
92      /* first byte */
93      i = begin - (first_byte * 8);
94      val = b->bits[first_byte];
95      val <<= i;
96      val >>= i;
97      ret += trueBitCount[val];
98
99      /* middle bytes */
100      for (i=first_byte+1; i<walk_end; ++i)
101        ret += trueBitCount[b->bits[i]];
102
103      /* last byte */
104      if (last_byte < b->alloc_count)
105        {
106          i = (last_byte+1)*8 - end;
107          val = b->bits[last_byte];
108          val >>= i;
109          val <<= i;
110          ret += trueBitCount[val];
111        }
112    }
113
114  assert (ret <= (begin - end));
115  return ret;
116}
117
118size_t
119tr_bitfieldCountRange (const tr_bitfield * b, size_t begin, size_t end)
120{
121  if (tr_bitfieldHasAll (b))
122    return end - begin;
123
124  if (tr_bitfieldHasNone (b))
125    return 0;
126
127  return countRange (b, begin, end);
128}
129
130bool
131tr_bitfieldHas (const tr_bitfield * b, size_t n)
132{
133  if (tr_bitfieldHasAll (b))
134    return true;
135
136  if (tr_bitfieldHasNone (b))
137    return false;
138
139  if (n>>3u >= b->alloc_count)
140    return false;
141
142  return (b->bits[n>>3u] << (n & 7u) & 0x80) != 0;
143}
144
145/***
146****
147***/
148
149static bool
150tr_bitfieldIsValid (const tr_bitfield * b UNUSED)
151{
152  assert (b != NULL);
153  assert ((b->alloc_count == 0) == (b->bits == 0));
154  assert (!b->bits || (b->true_count == countArray (b)));
155
156  return true;
157}
158
159size_t
160tr_bitfieldCountTrueBits (const tr_bitfield * b)
161{
162  assert (tr_bitfieldIsValid (b));
163
164  return b->true_count;
165}
166
167static size_t
168get_bytes_needed (size_t bit_count)
169{
170  return (bit_count >> 3) + (bit_count & 7 ? 1 : 0);
171}
172
173static void
174set_all_true (uint8_t * array, size_t bit_count)
175{
176  const uint8_t val = 0xFF;
177  const size_t n = get_bytes_needed (bit_count);
178
179  if (n > 0)
180    {
181      memset (array, val, n-1);
182
183      array[n-1] = val << (n*8 - bit_count);
184    }
185}
186
187void*
188tr_bitfieldGetRaw (const tr_bitfield * b, size_t * byte_count)
189{
190  const size_t n = get_bytes_needed (b->bit_count);
191  uint8_t * bits = tr_new0 (uint8_t, n);
192
193  assert (b->bit_count > 0);
194
195  if (b->alloc_count)
196    {
197      assert (b->alloc_count <= n);
198      memcpy (bits, b->bits, b->alloc_count);
199    }
200  else if (tr_bitfieldHasAll (b))
201    {
202      set_all_true (bits, b->bit_count);
203    }
204
205  *byte_count = n;
206  return bits;
207}
208
209static void
210tr_bitfieldEnsureBitsAlloced (tr_bitfield * b, size_t n)
211{
212  size_t bytes_needed;
213  const bool has_all = tr_bitfieldHasAll (b);
214
215  if (has_all)
216    bytes_needed = get_bytes_needed (MAX (n, b->true_count));
217  else
218    bytes_needed = get_bytes_needed (n);
219
220  if (b->alloc_count < bytes_needed)
221    {
222      b->bits = tr_renew (uint8_t, b->bits, bytes_needed);
223      memset (b->bits + b->alloc_count, 0, bytes_needed - b->alloc_count);
224      b->alloc_count = bytes_needed;
225
226      if (has_all)
227        set_all_true (b->bits, b->true_count);
228    }
229}
230
231static bool
232tr_bitfieldEnsureNthBitAlloced (tr_bitfield * b, size_t nth)
233{
234  /* count is zero-based, so we need to allocate nth+1 bits before setting the nth */
235
236  if (nth == SIZE_MAX)
237    return false;
238
239  tr_bitfieldEnsureBitsAlloced (b, nth + 1);
240  return true;
241}
242
243static void
244tr_bitfieldFreeArray (tr_bitfield * b)
245{
246  tr_free (b->bits);
247  b->bits = NULL;
248  b->alloc_count = 0;
249}
250
251static void
252tr_bitfieldSetTrueCount (tr_bitfield * b, size_t n)
253{
254  b->true_count = n;
255
256  if (tr_bitfieldHasAll (b) || tr_bitfieldHasNone (b))
257    tr_bitfieldFreeArray (b);
258
259  assert (tr_bitfieldIsValid (b));
260}
261
262static void
263tr_bitfieldRebuildTrueCount (tr_bitfield * b)
264{
265  tr_bitfieldSetTrueCount (b, countArray (b));
266}
267
268static void
269tr_bitfieldIncTrueCount (tr_bitfield * b, int i)
270{
271  tr_bitfieldSetTrueCount (b, b->true_count + i);
272}
273
274/****
275*****
276****/
277
278void
279tr_bitfieldConstruct (tr_bitfield * b, size_t bit_count)
280{
281  b->bit_count = bit_count;
282  b->true_count = 0;
283  b->bits = NULL;
284  b->alloc_count = 0;
285  b->have_all_hint = false;
286  b->have_none_hint = false;
287
288  assert (tr_bitfieldIsValid (b));
289}
290
291void
292tr_bitfieldSetHasNone (tr_bitfield * b)
293{
294  tr_bitfieldFreeArray (b);
295  b->true_count = 0;
296  b->have_all_hint = false;
297  b->have_none_hint = true;
298
299  assert (tr_bitfieldIsValid (b));
300}
301
302void
303tr_bitfieldSetHasAll (tr_bitfield * b)
304{
305  tr_bitfieldFreeArray (b);
306  b->true_count = b->bit_count;
307  b->have_all_hint = true;
308  b->have_none_hint = false;
309
310  assert (tr_bitfieldIsValid (b));
311}
312
313void
314tr_bitfieldSetFromBitfield (tr_bitfield * b, const tr_bitfield * src)
315{
316  if (tr_bitfieldHasAll (src))
317    tr_bitfieldSetHasAll (b);
318  else if (tr_bitfieldHasNone (src))
319    tr_bitfieldSetHasNone (b);
320  else
321    tr_bitfieldSetRaw (b, src->bits, src->alloc_count, true);
322}
323
324void
325tr_bitfieldSetRaw (tr_bitfield * b, const void * bits, size_t byte_count, bool bounded)
326{
327  tr_bitfieldFreeArray (b);
328  b->true_count = 0;
329
330  if (bounded)
331    byte_count = MIN (byte_count, get_bytes_needed (b->bit_count));
332
333  b->bits = tr_memdup (bits, byte_count);
334  b->alloc_count = byte_count;
335
336  if (bounded)
337    {
338      /* ensure the excess bits are set to '0' */
339      const int excess_bit_count = byte_count*8 - b->bit_count;
340      assert (excess_bit_count >= 0);
341      assert (excess_bit_count <= 7);
342      if (excess_bit_count)
343        b->bits[b->alloc_count-1] &= ((0xff) << excess_bit_count);
344    }
345
346  tr_bitfieldRebuildTrueCount (b);
347}
348
349void
350tr_bitfieldSetFromFlags (tr_bitfield * b, const bool * flags, size_t n)
351{
352  size_t i;
353  size_t trueCount = 0;
354
355  tr_bitfieldFreeArray (b);
356  tr_bitfieldEnsureBitsAlloced (b, n);
357
358  for (i=0; i<n; ++i)
359    {
360      if (flags[i])
361        {
362          ++trueCount;
363          b->bits[i >> 3u] |= (0x80 >> (i & 7u));
364        }
365    }
366
367  tr_bitfieldSetTrueCount (b, trueCount);
368}
369
370void
371tr_bitfieldAdd (tr_bitfield * b, size_t nth)
372{
373  if (!tr_bitfieldHas (b, nth) && tr_bitfieldEnsureNthBitAlloced (b, nth))
374    {
375      b->bits[nth >> 3u] |= (0x80 >> (nth & 7u));
376      tr_bitfieldIncTrueCount (b, 1);
377    }
378}
379
380/* Sets bit range [begin, end) to 1 */
381void
382tr_bitfieldAddRange (tr_bitfield * b, size_t begin, size_t end)
383{
384  size_t sb, eb;
385  unsigned char sm, em;
386  const size_t diff = (end-begin) - tr_bitfieldCountRange (b, begin, end);
387
388  if (diff == 0)
389    return;
390
391  end--;
392  if ((end >= b->bit_count) || (begin > end))
393    return;
394
395  sb = begin >> 3;
396  sm = ~ (0xff << (8 - (begin & 7)));
397  eb = end >> 3;
398  em = 0xff << (7 - (end & 7));
399
400  if (!tr_bitfieldEnsureNthBitAlloced (b, end))
401    return;
402
403  if (sb == eb)
404    {
405      b->bits[sb] |= (sm & em);
406    }
407  else
408    {
409      b->bits[sb] |= sm;
410      b->bits[eb] |= em;
411      if (++sb < eb)
412        memset (b->bits + sb, 0xff, eb - sb);
413    }
414
415  tr_bitfieldIncTrueCount (b, diff);
416}
417
418void
419tr_bitfieldRem (tr_bitfield * b, size_t nth)
420{
421  assert (tr_bitfieldIsValid (b));
422
423  if (!tr_bitfieldHas (b, nth) && tr_bitfieldEnsureNthBitAlloced (b, nth))
424    {
425      b->bits[nth >> 3u] &= (0xff7f >> (nth & 7u));
426      tr_bitfieldIncTrueCount (b, -1);
427    }
428}
429
430/* Clears bit range [begin, end) to 0 */
431void
432tr_bitfieldRemRange (tr_bitfield * b, size_t begin, size_t end)
433{
434  size_t sb, eb;
435  unsigned char sm, em;
436  const size_t diff = tr_bitfieldCountRange (b, begin, end);
437
438  if (!diff)
439    return;
440
441  end--;
442
443  if ((end >= b->bit_count) || (begin > end))
444    return;
445
446  sb = begin >> 3;
447  sm = 0xff << (8 - (begin & 7));
448  eb = end >> 3;
449  em = ~ (0xff << (7 - (end & 7)));
450
451  if (!tr_bitfieldEnsureNthBitAlloced (b, end))
452    return;
453
454  if (sb == eb)
455    {
456      b->bits[sb] &= (sm | em);
457    }
458  else
459    {
460      b->bits[sb] &= sm;
461      b->bits[eb] &= em;
462      if (++sb < eb)
463        memset (b->bits + sb, 0, eb - sb);
464    }
465
466  tr_bitfieldIncTrueCount (b, -diff);
467}
Note: See TracBrowser for help on using the repository browser.