source: trunk/libtransmission/bitfield.c @ 14532

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

Add more booleans to the picture

  • 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 14532 2015-05-31 22:13:31Z 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
149#ifndef NDEBUG
150
151static bool
152tr_bitfieldIsValid (const tr_bitfield * b)
153{
154  assert (b != NULL);
155  assert ((b->alloc_count == 0) == (b->bits == 0));
156  assert (!b->bits || (b->true_count == countArray (b)));
157
158  return true;
159}
160
161#endif
162
163size_t
164tr_bitfieldCountTrueBits (const tr_bitfield * b)
165{
166  assert (tr_bitfieldIsValid (b));
167
168  return b->true_count;
169}
170
171static size_t
172get_bytes_needed (size_t bit_count)
173{
174  return (bit_count >> 3) + (bit_count & 7 ? 1 : 0);
175}
176
177static void
178set_all_true (uint8_t * array, size_t bit_count)
179{
180  const uint8_t val = 0xFF;
181  const size_t n = get_bytes_needed (bit_count);
182
183  if (n > 0)
184    {
185      memset (array, val, n-1);
186
187      array[n-1] = val << (n*8 - bit_count);
188    }
189}
190
191void*
192tr_bitfieldGetRaw (const tr_bitfield * b, size_t * byte_count)
193{
194  const size_t n = get_bytes_needed (b->bit_count);
195  uint8_t * bits = tr_new0 (uint8_t, n);
196
197  assert (b->bit_count > 0);
198
199  if (b->alloc_count)
200    {
201      assert (b->alloc_count <= n);
202      memcpy (bits, b->bits, b->alloc_count);
203    }
204  else if (tr_bitfieldHasAll (b))
205    {
206      set_all_true (bits, b->bit_count);
207    }
208
209  *byte_count = n;
210  return bits;
211}
212
213static void
214tr_bitfieldEnsureBitsAlloced (tr_bitfield * b, size_t n)
215{
216  size_t bytes_needed;
217  const bool has_all = tr_bitfieldHasAll (b);
218
219  if (has_all)
220    bytes_needed = get_bytes_needed (MAX (n, b->true_count));
221  else
222    bytes_needed = get_bytes_needed (n);
223
224  if (b->alloc_count < bytes_needed)
225    {
226      b->bits = tr_renew (uint8_t, b->bits, bytes_needed);
227      memset (b->bits + b->alloc_count, 0, bytes_needed - b->alloc_count);
228      b->alloc_count = bytes_needed;
229
230      if (has_all)
231        set_all_true (b->bits, b->true_count);
232    }
233}
234
235static bool
236tr_bitfieldEnsureNthBitAlloced (tr_bitfield * b, size_t nth)
237{
238  /* count is zero-based, so we need to allocate nth+1 bits before setting the nth */
239
240  if (nth == SIZE_MAX)
241    return false;
242
243  tr_bitfieldEnsureBitsAlloced (b, nth + 1);
244  return true;
245}
246
247static void
248tr_bitfieldFreeArray (tr_bitfield * b)
249{
250  tr_free (b->bits);
251  b->bits = NULL;
252  b->alloc_count = 0;
253}
254
255static void
256tr_bitfieldSetTrueCount (tr_bitfield * b, size_t n)
257{
258  b->true_count = n;
259
260  if (tr_bitfieldHasAll (b) || tr_bitfieldHasNone (b))
261    tr_bitfieldFreeArray (b);
262
263  assert (tr_bitfieldIsValid (b));
264}
265
266static void
267tr_bitfieldRebuildTrueCount (tr_bitfield * b)
268{
269  tr_bitfieldSetTrueCount (b, countArray (b));
270}
271
272static void
273tr_bitfieldIncTrueCount (tr_bitfield * b, int i)
274{
275  tr_bitfieldSetTrueCount (b, b->true_count + i);
276}
277
278/****
279*****
280****/
281
282void
283tr_bitfieldConstruct (tr_bitfield * b, size_t bit_count)
284{
285  b->bit_count = bit_count;
286  b->true_count = 0;
287  b->bits = NULL;
288  b->alloc_count = 0;
289  b->have_all_hint = false;
290  b->have_none_hint = false;
291
292  assert (tr_bitfieldIsValid (b));
293}
294
295void
296tr_bitfieldSetHasNone (tr_bitfield * b)
297{
298  tr_bitfieldFreeArray (b);
299  b->true_count = 0;
300  b->have_all_hint = false;
301  b->have_none_hint = true;
302
303  assert (tr_bitfieldIsValid (b));
304}
305
306void
307tr_bitfieldSetHasAll (tr_bitfield * b)
308{
309  tr_bitfieldFreeArray (b);
310  b->true_count = b->bit_count;
311  b->have_all_hint = true;
312  b->have_none_hint = false;
313
314  assert (tr_bitfieldIsValid (b));
315}
316
317void
318tr_bitfieldSetFromBitfield (tr_bitfield * b, const tr_bitfield * src)
319{
320  if (tr_bitfieldHasAll (src))
321    tr_bitfieldSetHasAll (b);
322  else if (tr_bitfieldHasNone (src))
323    tr_bitfieldSetHasNone (b);
324  else
325    tr_bitfieldSetRaw (b, src->bits, src->alloc_count, true);
326}
327
328void
329tr_bitfieldSetRaw (tr_bitfield * b, const void * bits, size_t byte_count, bool bounded)
330{
331  tr_bitfieldFreeArray (b);
332  b->true_count = 0;
333
334  if (bounded)
335    byte_count = MIN (byte_count, get_bytes_needed (b->bit_count));
336
337  b->bits = tr_memdup (bits, byte_count);
338  b->alloc_count = byte_count;
339
340  if (bounded)
341    {
342      /* ensure the excess bits are set to '0' */
343      const int excess_bit_count = byte_count*8 - b->bit_count;
344      assert (excess_bit_count >= 0);
345      assert (excess_bit_count <= 7);
346      if (excess_bit_count)
347        b->bits[b->alloc_count-1] &= ((0xff) << excess_bit_count);
348    }
349
350  tr_bitfieldRebuildTrueCount (b);
351}
352
353void
354tr_bitfieldSetFromFlags (tr_bitfield * b, const bool * flags, size_t n)
355{
356  size_t i;
357  size_t trueCount = 0;
358
359  tr_bitfieldFreeArray (b);
360  tr_bitfieldEnsureBitsAlloced (b, n);
361
362  for (i=0; i<n; ++i)
363    {
364      if (flags[i])
365        {
366          ++trueCount;
367          b->bits[i >> 3u] |= (0x80 >> (i & 7u));
368        }
369    }
370
371  tr_bitfieldSetTrueCount (b, trueCount);
372}
373
374void
375tr_bitfieldAdd (tr_bitfield * b, size_t nth)
376{
377  if (!tr_bitfieldHas (b, nth) && tr_bitfieldEnsureNthBitAlloced (b, nth))
378    {
379      b->bits[nth >> 3u] |= (0x80 >> (nth & 7u));
380      tr_bitfieldIncTrueCount (b, 1);
381    }
382}
383
384/* Sets bit range [begin, end) to 1 */
385void
386tr_bitfieldAddRange (tr_bitfield * b, size_t begin, size_t end)
387{
388  size_t sb, eb;
389  unsigned char sm, em;
390  const size_t diff = (end-begin) - tr_bitfieldCountRange (b, begin, end);
391
392  if (diff == 0)
393    return;
394
395  end--;
396  if ((end >= b->bit_count) || (begin > end))
397    return;
398
399  sb = begin >> 3;
400  sm = ~ (0xff << (8 - (begin & 7)));
401  eb = end >> 3;
402  em = 0xff << (7 - (end & 7));
403
404  if (!tr_bitfieldEnsureNthBitAlloced (b, end))
405    return;
406
407  if (sb == eb)
408    {
409      b->bits[sb] |= (sm & em);
410    }
411  else
412    {
413      b->bits[sb] |= sm;
414      b->bits[eb] |= em;
415      if (++sb < eb)
416        memset (b->bits + sb, 0xff, eb - sb);
417    }
418
419  tr_bitfieldIncTrueCount (b, diff);
420}
421
422void
423tr_bitfieldRem (tr_bitfield * b, size_t nth)
424{
425  assert (tr_bitfieldIsValid (b));
426
427  if (!tr_bitfieldHas (b, nth) && tr_bitfieldEnsureNthBitAlloced (b, nth))
428    {
429      b->bits[nth >> 3u] &= (0xff7f >> (nth & 7u));
430      tr_bitfieldIncTrueCount (b, -1);
431    }
432}
433
434/* Clears bit range [begin, end) to 0 */
435void
436tr_bitfieldRemRange (tr_bitfield * b, size_t begin, size_t end)
437{
438  size_t sb, eb;
439  unsigned char sm, em;
440  const size_t diff = tr_bitfieldCountRange (b, begin, end);
441
442  if (!diff)
443    return;
444
445  end--;
446
447  if ((end >= b->bit_count) || (begin > end))
448    return;
449
450  sb = begin >> 3;
451  sm = 0xff << (8 - (begin & 7));
452  eb = end >> 3;
453  em = ~ (0xff << (7 - (end & 7)));
454
455  if (!tr_bitfieldEnsureNthBitAlloced (b, end))
456    return;
457
458  if (sb == eb)
459    {
460      b->bits[sb] &= (sm | em);
461    }
462  else
463    {
464      b->bits[sb] &= sm;
465      b->bits[eb] &= em;
466      if (++sb < eb)
467        memset (b->bits + sb, 0, eb - sb);
468    }
469
470  tr_bitfieldIncTrueCount (b, -diff);
471}
Note: See TracBrowser for help on using the repository browser.