source: trunk/libtransmission/bitfield.c

Last change on this file was 14646, checked in by mikedld, 5 years ago

Loosen bitfield assertions to account for unknown bit counts

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