xref: /haiku/src/libs/zydis/Zycore/Bitset.c (revision 909af08f4328301fbdef1ffb41f566c3b5bec0c7) 
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 /* ============================================================================================== */
671