1  /***************************************************************************************************
  2  
  3    Zyan Core Library (Zycore-C)
  4  
  5    Original Author : Florian Bernd
  6  
  7   * Permission is hereby granted, free of charge, to any person obtaining a copy
  8   * of this software and associated documentation files (the "Software"), to deal
  9   * in the Software without restriction, including without limitation the rights
 10   * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 11   * copies of the Software, and to permit persons to whom the Software is
 12   * furnished to do so, subject to the following conditions:
 13   *
 14   * The above copyright notice and this permission notice shall be included in all
 15   * copies or substantial portions of the Software.
 16   *
 17   * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 18   * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 19   * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 20   * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 21   * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 22   * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 23   * SOFTWARE.
 24  
 25  ***************************************************************************************************/
 26  
 27  #include <Zycore/Bitset.h>
 28  #include <Zycore/LibC.h>
 29  
 30  /* ============================================================================================== */
 31  /* Internal constants                                                                             */
 32  /* ============================================================================================== */
 33  
 34  #define ZYAN_BITSET_GROWTH_FACTOR    2
 35  #define ZYAN_BITSET_SHRINK_THRESHOLD 2
 36  
 37  /* ============================================================================================== */
 38  /* Internal macros                                                                                */
 39  /* ============================================================================================== */
 40  
 41  /**
 42   * Computes the smallest integer value not less than `x`.
 43   *
 44   * @param   x   The value.
 45   *
 46   * @return  The smallest integer value not less than `x`.
 47   */
 48  #define ZYAN_BITSET_CEIL(x) \
 49      (((x) == ((ZyanU32)(x))) ? (ZyanU32)(x) : ((ZyanU32)(x)) + 1)
 50  
 51  /**
 52   * Converts bits to bytes.
 53   *
 54   * @param   x   The value in bits.
 55   *
 56   * @return  The amount of bytes needed to fit `x` bits.
 57   */
 58  #define ZYAN_BITSET_BITS_TO_BYTES(x) \
 59      ZYAN_BITSET_CEIL((x) / 8)
 60  
 61  /**
 62   * Returns the offset of the given bit.
 63   *
 64   * @param   index   The bit index.
 65   *
 66   * @return  The offset of the given bit.
 67   */
 68  #define ZYAN_BITSET_BIT_OFFSET(index) \
 69      (7 - ((index) % 8))
 70  
 71  /* ============================================================================================== */
 72  /* Internal functions                                                                             */
 73  /* ============================================================================================== */
 74  
 75  /* ---------------------------------------------------------------------------------------------- */
 76  /* Helper functions                                                                               */
 77  /* ---------------------------------------------------------------------------------------------- */
 78  
 79  /**
 80   * Initializes the given `vector` with `count` "zero"-bytes.
 81   *
 82   * @param   vector  A pointer to the `ZyanVector` instance.
 83   * @param   count   The number of bytes.
 84   *
 85   * @return  A zyan status code.
 86   */
 87  static ZyanStatus ZyanBitsetInitVectorElements(ZyanVector* vector, ZyanUSize count)
 88  {
 89      ZYAN_ASSERT(vector);
 90  
 91      static const ZyanU8 zero = 0;
 92      for (ZyanUSize i = 0; i < count; ++i)
 93      {
 94          ZYAN_CHECK(ZyanVectorPushBack(vector, &zero));
 95      }
 96  
 97      return ZYAN_STATUS_SUCCESS;
 98  }
 99  
100  /* ---------------------------------------------------------------------------------------------- */
101  /* Byte operations                                                                                */
102  /* ---------------------------------------------------------------------------------------------- */
103  
104  static ZyanStatus ZyanBitsetOperationAND(ZyanU8* b1, const ZyanU8* b2)
105  {
106      *b1 &= *b2;
107      return ZYAN_STATUS_SUCCESS;
108  }
109  
110  static ZyanStatus ZyanBitsetOperationOR (ZyanU8* b1, const ZyanU8* b2)
111  {
112      *b1 |= *b2;
113      return ZYAN_STATUS_SUCCESS;
114  }
115  
116  static ZyanStatus ZyanBitsetOperationXOR(ZyanU8* b1, const ZyanU8* b2)
117  {
118      *b1 ^= *b2;
119      return ZYAN_STATUS_SUCCESS;
120  }
121  
122  /* ---------------------------------------------------------------------------------------------- */
123  
124  /* ============================================================================================== */
125  /* Exported functions                                                                             */
126  /* ============================================================================================== */
127  
128  /* ---------------------------------------------------------------------------------------------- */
129  /* Constructor and destructor                                                                     */
130  /* ---------------------------------------------------------------------------------------------- */
131  
132  #ifndef ZYAN_NO_LIBC
133  
134  ZyanStatus ZyanBitsetInit(ZyanBitset* bitset, ZyanUSize count)
135  {
136      return ZyanBitsetInitEx(bitset, count, ZyanAllocatorDefault(), ZYAN_BITSET_GROWTH_FACTOR,
137          ZYAN_BITSET_SHRINK_THRESHOLD);
138  }
139  
140  #endif // ZYAN_NO_LIBC
141  
142  ZyanStatus ZyanBitsetInitEx(ZyanBitset* bitset, ZyanUSize count, ZyanAllocator* allocator,
143      ZyanU8 growth_factor, ZyanU8 shrink_threshold)
144  {
145      if (!bitset)
146      {
147          return ZYAN_STATUS_INVALID_ARGUMENT;
148      }
149  
150      const ZyanU32 bytes = ZYAN_BITSET_BITS_TO_BYTES(count);
151  
152      bitset->size = count;
153      ZYAN_CHECK(ZyanVectorInitEx(&bitset->bits, sizeof(ZyanU8), bytes, ZYAN_NULL, allocator,
154          growth_factor, shrink_threshold));
155      ZYAN_CHECK(ZyanBitsetInitVectorElements(&bitset->bits, bytes));
156  
157      return ZYAN_STATUS_SUCCESS;
158  }
159  
160  ZyanStatus ZyanBitsetInitBuffer(ZyanBitset* bitset, ZyanUSize count, void* buffer,
161      ZyanUSize capacity)
162  {
163      if (!bitset)
164      {
165          return ZYAN_STATUS_INVALID_ARGUMENT;
166      }
167  
168      const ZyanU32 bytes = ZYAN_BITSET_BITS_TO_BYTES(count);
169      if (capacity < bytes)
170      {
171          return ZYAN_STATUS_INSUFFICIENT_BUFFER_SIZE;
172      }
173  
174      bitset->size = count;
175      ZYAN_CHECK(ZyanVectorInitCustomBuffer(&bitset->bits, sizeof(ZyanU8), buffer, capacity,
176          ZYAN_NULL));
177      ZYAN_CHECK(ZyanBitsetInitVectorElements(&bitset->bits, bytes));
178  
179      return ZYAN_STATUS_SUCCESS;
180  }
181  
182  ZyanStatus ZyanBitsetDestroy(ZyanBitset* bitset)
183  {
184      if (!bitset)
185      {
186          return ZYAN_STATUS_INVALID_ARGUMENT;
187      }
188  
189      return ZyanVectorDestroy(&bitset->bits);
190  }
191  
192  /* ---------------------------------------------------------------------------------------------- */
193  /* Logical operations                                                                             */
194  /* ---------------------------------------------------------------------------------------------- */
195  
196  ZyanStatus ZyanBitsetPerformByteOperation(ZyanBitset* destination, const ZyanBitset* source,
197      ZyanBitsetByteOperation operation)
198  {
199      if (!destination || !source || !operation)
200      {
201          return ZYAN_STATUS_INVALID_ARGUMENT;
202      }
203  
204      ZyanUSize s1;
205      ZyanUSize s2;
206      ZYAN_CHECK(ZyanVectorGetSize(&destination->bits, &s1));
207      ZYAN_CHECK(ZyanVectorGetSize(&source->bits, &s2));
208  
209      const ZyanUSize min = ZYAN_MIN(s1, s2);
210      for (ZyanUSize i = 0; i < min; ++i)
211      {
212          ZyanU8* v1;
213          const ZyanU8* v2;
214          ZYAN_CHECK(ZyanVectorGetPointerMutable(&destination->bits, i, (void**)&v1));
215          ZYAN_CHECK(ZyanVectorGetPointer(&source->bits, i, (const void**)&v2));
216  
217          ZYAN_ASSERT(v1);
218          ZYAN_ASSERT(v2);
219  
220          ZYAN_CHECK(operation(v1, v2));
221      }
222  
223      return ZYAN_STATUS_SUCCESS;
224  }
225  
226  ZyanStatus ZyanBitsetAND(ZyanBitset* destination, const ZyanBitset* source)
227  {
228      return ZyanBitsetPerformByteOperation(destination, source, ZyanBitsetOperationAND);
229  }
230  
231  ZyanStatus ZyanBitsetOR (ZyanBitset* destination, const ZyanBitset* source)
232  {
233      return ZyanBitsetPerformByteOperation(destination, source, ZyanBitsetOperationOR );
234  }
235  
236  ZyanStatus ZyanBitsetXOR(ZyanBitset* destination, const ZyanBitset* source)
237  {
238      return ZyanBitsetPerformByteOperation(destination, source, ZyanBitsetOperationXOR);
239  }
240  
241  ZyanStatus ZyanBitsetFlip(ZyanBitset* bitset)
242  {
243      if (!bitset)
244      {
245          return ZYAN_STATUS_INVALID_ARGUMENT;
246      }
247  
248      ZyanUSize size;
249      ZYAN_CHECK(ZyanVectorGetSize(&bitset->bits, &size));
250      for (ZyanUSize i = 0; i < size; ++i)
251      {
252          ZyanU8* value;
253          ZYAN_CHECK(ZyanVectorGetPointerMutable(&bitset->bits, i, (void**)&value));
254          *value = ~(*value);
255      }
256  
257      return ZYAN_STATUS_SUCCESS;
258  }
259  
260  /* ---------------------------------------------------------------------------------------------- */
261  /* Bit access                                                                                     */
262  /* ---------------------------------------------------------------------------------------------- */
263  
264  ZyanStatus ZyanBitsetSet(ZyanBitset* bitset, ZyanUSize index)
265  {
266      if (!bitset)
267      {
268          return ZYAN_STATUS_INVALID_ARGUMENT;
269      }
270      if (index >= bitset->size)
271      {
272          return ZYAN_STATUS_OUT_OF_RANGE;
273      }
274  
275      ZyanU8* value;
276      ZYAN_CHECK(ZyanVectorGetPointerMutable(&bitset->bits, index / 8, (void**)&value));
277  
278      *value |= (1 << ZYAN_BITSET_BIT_OFFSET(index));
279  
280      return ZYAN_STATUS_SUCCESS;
281  }
282  
283  ZyanStatus ZyanBitsetReset(ZyanBitset* bitset, ZyanUSize index)
284  {
285      if (!bitset)
286      {
287          return ZYAN_STATUS_INVALID_ARGUMENT;
288      }
289      if (index >= bitset->size)
290      {
291          return ZYAN_STATUS_OUT_OF_RANGE;
292      }
293  
294      ZyanU8* value;
295      ZYAN_CHECK(ZyanVectorGetPointerMutable(&bitset->bits, index / 8, (void**)&value));
296      *value &= ~(1 << ZYAN_BITSET_BIT_OFFSET(index));
297  
298      return ZYAN_STATUS_SUCCESS;
299  }
300  
301  ZyanStatus ZyanBitsetAssign(ZyanBitset* bitset, ZyanUSize index, ZyanBool value)
302  {
303      if (value)
304      {
305          return ZyanBitsetSet(bitset, index);
306      }
307      return ZyanBitsetReset(bitset, index);
308  }
309  
310  ZyanStatus ZyanBitsetToggle(ZyanBitset* bitset, ZyanUSize index)
311  {
312      if (!bitset)
313      {
314          return ZYAN_STATUS_INVALID_ARGUMENT;
315      }
316      if (index >= bitset->size)
317      {
318          return ZYAN_STATUS_OUT_OF_RANGE;
319      }
320  
321      ZyanU8* value;
322      ZYAN_CHECK(ZyanVectorGetPointerMutable(&bitset->bits, index / 8, (void**)&value));
323      *value ^= (1 << ZYAN_BITSET_BIT_OFFSET(index));
324  
325      return ZYAN_STATUS_SUCCESS;
326  }
327  
328  ZyanStatus ZyanBitsetTest(ZyanBitset* bitset, ZyanUSize index)
329  {
330      if (!bitset)
331      {
332          return ZYAN_STATUS_INVALID_ARGUMENT;
333      }
334      if (index >= bitset->size)
335      {
336          return ZYAN_STATUS_OUT_OF_RANGE;
337      }
338  
339      const ZyanU8* value;
340      ZYAN_CHECK(ZyanVectorGetPointer(&bitset->bits, index / 8, (const void**)&value));
341      if ((*value & (1 << ZYAN_BITSET_BIT_OFFSET(index))) == 0)
342      {
343          return ZYAN_STATUS_FALSE;
344      }
345      return ZYAN_STATUS_TRUE;
346  }
347  
348  ZyanStatus ZyanBitsetTestMSB(ZyanBitset* bitset)
349  {
350      if (!bitset)
351      {
352          return ZYAN_STATUS_INVALID_ARGUMENT;
353      }
354  
355      return ZyanBitsetTest(bitset, bitset->size - 1);
356  }
357  
358  ZyanStatus ZyanBitsetTestLSB(ZyanBitset* bitset)
359  {
360      return ZyanBitsetTest(bitset, 0);
361  }
362  
363  /* ---------------------------------------------------------------------------------------------- */
364  
365  ZyanStatus ZyanBitsetSetAll(ZyanBitset* bitset)
366  {
367      if (!bitset)
368      {
369          return ZYAN_STATUS_INVALID_ARGUMENT;
370      }
371  
372      ZyanUSize size;
373      ZYAN_CHECK(ZyanVectorGetSize(&bitset->bits, &size));
374      for (ZyanUSize i = 0; i < size; ++i)
375      {
376          ZyanU8* value;
377          ZYAN_CHECK(ZyanVectorGetPointerMutable(&bitset->bits, i, (void**)&value));
378          *value = 0xFF;
379      }
380  
381      return ZYAN_STATUS_SUCCESS;
382  }
383  
384  ZyanStatus ZyanBitsetResetAll(ZyanBitset* bitset)
385  {
386      if (!bitset)
387      {
388          return ZYAN_STATUS_INVALID_ARGUMENT;
389      }
390  
391      ZyanUSize size;
392      ZYAN_CHECK(ZyanVectorGetSize(&bitset->bits, &size));
393      for (ZyanUSize i = 0; i < size; ++i)
394      {
395          ZyanU8* value;
396          ZYAN_CHECK(ZyanVectorGetPointerMutable(&bitset->bits, i, (void**)&value));
397          *value = 0x00;
398      }
399  
400      return ZYAN_STATUS_SUCCESS;
401  }
402  
403  /* ---------------------------------------------------------------------------------------------- */
404  /* Size management                                                                                */
405  /* ---------------------------------------------------------------------------------------------- */
406  
407  ZyanStatus ZyanBitsetPush(ZyanBitset* bitset, ZyanBool value)
408  {
409      if (!bitset)
410      {
411          return ZYAN_STATUS_INVALID_ARGUMENT;
412      }
413  
414      if ((bitset->size++ % 8) == 0)
415      {
416          static const ZyanU8 zero = 0;
417          ZYAN_CHECK(ZyanVectorPushBack(&bitset->bits, &zero));
418      }
419  
420      return ZyanBitsetAssign(bitset, bitset->size - 1, value);
421  }
422  
423  ZyanStatus ZyanBitsetPop(ZyanBitset* bitset)
424  {
425      if (!bitset)
426      {
427          return ZYAN_STATUS_INVALID_ARGUMENT;
428      }
429  
430      if ((--bitset->size % 8) == 0)
431      {
432          return ZyanVectorPopBack(&bitset->bits);
433      }
434  
435      return ZYAN_STATUS_SUCCESS;
436  }
437  
438  ZyanStatus ZyanBitsetClear(ZyanBitset* bitset)
439  {
440      if (!bitset)
441      {
442          return ZYAN_STATUS_INVALID_ARGUMENT;
443      }
444  
445      bitset->size = 0;
446      return ZyanVectorClear(&bitset->bits);
447  }
448  
449  /* ---------------------------------------------------------------------------------------------- */
450  /* Memory management                                                                              */
451  /* ---------------------------------------------------------------------------------------------- */
452  
453  ZyanStatus ZyanBitsetReserve(ZyanBitset* bitset, ZyanUSize count)
454  {
455      return ZyanVectorReserve(&bitset->bits, ZYAN_BITSET_BITS_TO_BYTES(count));
456  }
457  
458  ZyanStatus ZyanBitsetShrinkToFit(ZyanBitset* bitset)
459  {
460      return ZyanVectorShrinkToFit(&bitset->bits);
461  }
462  
463  /* ---------------------------------------------------------------------------------------------- */
464  /* Information                                                                                    */
465  /* ---------------------------------------------------------------------------------------------- */
466  
467  ZyanStatus ZyanBitsetGetSize(const ZyanBitset* bitset, ZyanUSize* size)
468  {
469      if (!bitset)
470      {
471          return ZYAN_STATUS_INVALID_ARGUMENT;
472      }
473  
474      *size = bitset->size;
475  
476      return ZYAN_STATUS_SUCCESS;
477  }
478  
479  ZyanStatus ZyanBitsetGetCapacity(const ZyanBitset* bitset, ZyanUSize* capacity)
480  {
481      ZYAN_CHECK(ZyanBitsetGetCapacityBytes(bitset, capacity));
482      *capacity *= 8;
483  
484      return ZYAN_STATUS_SUCCESS;
485  }
486  
487  ZyanStatus ZyanBitsetGetSizeBytes(const ZyanBitset* bitset, ZyanUSize* size)
488  {
489      if (!bitset)
490      {
491          return ZYAN_STATUS_INVALID_ARGUMENT;
492      }
493  
494      return ZyanVectorGetSize(&bitset->bits, size);
495  }
496  
497  ZyanStatus ZyanBitsetGetCapacityBytes(const ZyanBitset* bitset, ZyanUSize* capacity)
498  {
499      if (!bitset)
500      {
501          return ZYAN_STATUS_INVALID_ARGUMENT;
502      }
503  
504      return ZyanVectorGetCapacity(&bitset->bits, capacity);
505  }
506  
507  /* ---------------------------------------------------------------------------------------------- */
508  
509  ZyanStatus ZyanBitsetCount(const ZyanBitset* bitset, ZyanUSize* count)
510  {
511      if (!bitset || !count)
512      {
513          return ZYAN_STATUS_INVALID_ARGUMENT;
514      }
515  
516      *count = 0;
517  
518      ZyanUSize size;
519      ZYAN_CHECK(ZyanVectorGetSize(&bitset->bits, &size));
520      for (ZyanUSize i = 0; i < size; ++i)
521      {
522          ZyanU8* value;
523          ZYAN_CHECK(ZyanVectorGetPointer(&bitset->bits, i, (const void**)&value));
524  
525          ZyanU8 popcnt = *value;
526          popcnt = (popcnt & 0x55) + ((popcnt >> 1) & 0x55);
527          popcnt = (popcnt & 0x33) + ((popcnt >> 2) & 0x33);
528          popcnt = (popcnt & 0x0F) + ((popcnt >> 4) & 0x0F);
529  
530          *count += popcnt;
531      }
532  
533      *count = ZYAN_MIN(*count, bitset->size);
534  
535      return ZYAN_STATUS_SUCCESS;
536  }
537  
538  ZyanStatus ZyanBitsetAll(const ZyanBitset* bitset)
539  {
540      if (!bitset)
541      {
542          return ZYAN_STATUS_INVALID_ARGUMENT;
543      }
544  
545      ZyanUSize size;
546      ZYAN_CHECK(ZyanVectorGetSize(&bitset->bits, &size));
547      for (ZyanUSize i = 0; i < size; ++i)
548      {
549          ZyanU8* value;
550          ZYAN_CHECK(ZyanVectorGetPointer(&bitset->bits, i, (const void**)&value));
551          if (i < (size - 1))
552          {
553              if (*value != 0xFF)
554              {
555                  return ZYAN_STATUS_FALSE;
556              }
557          } else
558          {
559              const ZyanU8 mask = ~(8 - (bitset->size % 8));
560              if ((*value & mask) != mask)
561              {
562                  return ZYAN_STATUS_FALSE;
563              }
564          }
565      }
566  
567      return ZYAN_STATUS_TRUE;
568  }
569  
570  ZyanStatus ZyanBitsetAny(const ZyanBitset* bitset)
571  {
572      if (!bitset)
573      {
574          return ZYAN_STATUS_INVALID_ARGUMENT;
575      }
576  
577      ZyanUSize size;
578      ZYAN_CHECK(ZyanVectorGetSize(&bitset->bits, &size));
579      for (ZyanUSize i = 0; i < size; ++i)
580      {
581          ZyanU8* value;
582          ZYAN_CHECK(ZyanVectorGetPointer(&bitset->bits, i, (const void**)&value));
583          if (i < (size - 1))
584          {
585              if (*value != 0x00)
586              {
587                  return ZYAN_STATUS_TRUE;
588              }
589          } else
590          {
591              const ZyanU8 mask = ~(8 - (bitset->size % 8));
592              if ((*value & mask) != 0x00)
593              {
594                  return ZYAN_STATUS_TRUE;
595              }
596          }
597      }
598  
599      return ZYAN_STATUS_FALSE;
600  }
601  
602  ZyanStatus ZyanBitsetNone(const ZyanBitset* bitset)
603  {
604      if (!bitset)
605      {
606          return ZYAN_STATUS_INVALID_ARGUMENT;
607      }
608  
609      ZyanUSize size;
610      ZYAN_CHECK(ZyanVectorGetSize(&bitset->bits, &size));
611      for (ZyanUSize i = 0; i < size; ++i)
612      {
613          ZyanU8* value;
614          ZYAN_CHECK(ZyanVectorGetPointer(&bitset->bits, i, (const void**)&value));
615          if (i < (size - 1))
616          {
617              if (*value != 0x00)
618              {
619                  return ZYAN_STATUS_FALSE;
620              }
621          } else
622          {
623              const ZyanU8 mask = ~(8 - (bitset->size % 8));
624              if ((*value & mask) != 0x00)
625              {
626                  return ZYAN_STATUS_FALSE;
627              }
628          }
629      }
630  
631      return ZYAN_STATUS_TRUE;
632  }
633  
634  /* ---------------------------------------------------------------------------------------------- */
635  
636  //ZyanStatus ZyanBitsetToU32(const ZyanBitset* bitset, ZyanU32* value)
637  //{
638  //    if (!bitset)
639  //    {
640  //        return ZYAN_STATUS_INVALID_ARGUMENT;
641  //    }
642  //    if (bitset->size > 32)
643  //    {
644  //        return ZYAN_STATUS_INVALID_OPERATION;
645  //    }
646  //
647  //    // TODO:
648  //
649  //    return ZYAN_STATUS_SUCCESS;
650  //}
651  //
652  //ZyanStatus ZyanBitsetToU64(const ZyanBitset* bitset, ZyanU64* value)
653  //{
654  //    if (!bitset)
655  //    {
656  //        return ZYAN_STATUS_INVALID_ARGUMENT;
657  //    }
658  //    if (bitset->size > 64)
659  //    {
660  //        return ZYAN_STATUS_INVALID_OPERATION;
661  //    }
662  //
663  //    // TODO:
664  //
665  //    return ZYAN_STATUS_SUCCESS;
666  //}
667  
668  /* ---------------------------------------------------------------------------------------------- */
669  
670  /* ============================================================================================== */