source: trunk/libtransmission/bitfield.c @ 13637

Last change on this file since 13637 was 13637, checked in by jordan, 9 years ago

in bitfield.c, speed up countArray() by about 15%

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