croaring-ffi-1.0: cbits/CRoaring/src/bitset_util.c
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <roaring/bitset_util.h>
#if CROARING_IS_X64
#ifndef CROARING_COMPILER_SUPPORTS_AVX512
#error "CROARING_COMPILER_SUPPORTS_AVX512 needs to be defined."
#endif // CROARING_COMPILER_SUPPORTS_AVX512
#endif
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wuninitialized"
#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
#endif
#ifdef __cplusplus
using namespace ::roaring::internal;
extern "C" {
namespace roaring {
namespace api {
#endif
#if CROARING_IS_X64
static uint8_t lengthTable[256] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4,
2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4,
2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5,
3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
#endif
#if CROARING_IS_X64
ALIGNED(32)
static uint32_t vecDecodeTable[256][8] = {
{0, 0, 0, 0, 0, 0, 0, 0}, /* 0x00 (00000000) */
{1, 0, 0, 0, 0, 0, 0, 0}, /* 0x01 (00000001) */
{2, 0, 0, 0, 0, 0, 0, 0}, /* 0x02 (00000010) */
{1, 2, 0, 0, 0, 0, 0, 0}, /* 0x03 (00000011) */
{3, 0, 0, 0, 0, 0, 0, 0}, /* 0x04 (00000100) */
{1, 3, 0, 0, 0, 0, 0, 0}, /* 0x05 (00000101) */
{2, 3, 0, 0, 0, 0, 0, 0}, /* 0x06 (00000110) */
{1, 2, 3, 0, 0, 0, 0, 0}, /* 0x07 (00000111) */
{4, 0, 0, 0, 0, 0, 0, 0}, /* 0x08 (00001000) */
{1, 4, 0, 0, 0, 0, 0, 0}, /* 0x09 (00001001) */
{2, 4, 0, 0, 0, 0, 0, 0}, /* 0x0A (00001010) */
{1, 2, 4, 0, 0, 0, 0, 0}, /* 0x0B (00001011) */
{3, 4, 0, 0, 0, 0, 0, 0}, /* 0x0C (00001100) */
{1, 3, 4, 0, 0, 0, 0, 0}, /* 0x0D (00001101) */
{2, 3, 4, 0, 0, 0, 0, 0}, /* 0x0E (00001110) */
{1, 2, 3, 4, 0, 0, 0, 0}, /* 0x0F (00001111) */
{5, 0, 0, 0, 0, 0, 0, 0}, /* 0x10 (00010000) */
{1, 5, 0, 0, 0, 0, 0, 0}, /* 0x11 (00010001) */
{2, 5, 0, 0, 0, 0, 0, 0}, /* 0x12 (00010010) */
{1, 2, 5, 0, 0, 0, 0, 0}, /* 0x13 (00010011) */
{3, 5, 0, 0, 0, 0, 0, 0}, /* 0x14 (00010100) */
{1, 3, 5, 0, 0, 0, 0, 0}, /* 0x15 (00010101) */
{2, 3, 5, 0, 0, 0, 0, 0}, /* 0x16 (00010110) */
{1, 2, 3, 5, 0, 0, 0, 0}, /* 0x17 (00010111) */
{4, 5, 0, 0, 0, 0, 0, 0}, /* 0x18 (00011000) */
{1, 4, 5, 0, 0, 0, 0, 0}, /* 0x19 (00011001) */
{2, 4, 5, 0, 0, 0, 0, 0}, /* 0x1A (00011010) */
{1, 2, 4, 5, 0, 0, 0, 0}, /* 0x1B (00011011) */
{3, 4, 5, 0, 0, 0, 0, 0}, /* 0x1C (00011100) */
{1, 3, 4, 5, 0, 0, 0, 0}, /* 0x1D (00011101) */
{2, 3, 4, 5, 0, 0, 0, 0}, /* 0x1E (00011110) */
{1, 2, 3, 4, 5, 0, 0, 0}, /* 0x1F (00011111) */
{6, 0, 0, 0, 0, 0, 0, 0}, /* 0x20 (00100000) */
{1, 6, 0, 0, 0, 0, 0, 0}, /* 0x21 (00100001) */
{2, 6, 0, 0, 0, 0, 0, 0}, /* 0x22 (00100010) */
{1, 2, 6, 0, 0, 0, 0, 0}, /* 0x23 (00100011) */
{3, 6, 0, 0, 0, 0, 0, 0}, /* 0x24 (00100100) */
{1, 3, 6, 0, 0, 0, 0, 0}, /* 0x25 (00100101) */
{2, 3, 6, 0, 0, 0, 0, 0}, /* 0x26 (00100110) */
{1, 2, 3, 6, 0, 0, 0, 0}, /* 0x27 (00100111) */
{4, 6, 0, 0, 0, 0, 0, 0}, /* 0x28 (00101000) */
{1, 4, 6, 0, 0, 0, 0, 0}, /* 0x29 (00101001) */
{2, 4, 6, 0, 0, 0, 0, 0}, /* 0x2A (00101010) */
{1, 2, 4, 6, 0, 0, 0, 0}, /* 0x2B (00101011) */
{3, 4, 6, 0, 0, 0, 0, 0}, /* 0x2C (00101100) */
{1, 3, 4, 6, 0, 0, 0, 0}, /* 0x2D (00101101) */
{2, 3, 4, 6, 0, 0, 0, 0}, /* 0x2E (00101110) */
{1, 2, 3, 4, 6, 0, 0, 0}, /* 0x2F (00101111) */
{5, 6, 0, 0, 0, 0, 0, 0}, /* 0x30 (00110000) */
{1, 5, 6, 0, 0, 0, 0, 0}, /* 0x31 (00110001) */
{2, 5, 6, 0, 0, 0, 0, 0}, /* 0x32 (00110010) */
{1, 2, 5, 6, 0, 0, 0, 0}, /* 0x33 (00110011) */
{3, 5, 6, 0, 0, 0, 0, 0}, /* 0x34 (00110100) */
{1, 3, 5, 6, 0, 0, 0, 0}, /* 0x35 (00110101) */
{2, 3, 5, 6, 0, 0, 0, 0}, /* 0x36 (00110110) */
{1, 2, 3, 5, 6, 0, 0, 0}, /* 0x37 (00110111) */
{4, 5, 6, 0, 0, 0, 0, 0}, /* 0x38 (00111000) */
{1, 4, 5, 6, 0, 0, 0, 0}, /* 0x39 (00111001) */
{2, 4, 5, 6, 0, 0, 0, 0}, /* 0x3A (00111010) */
{1, 2, 4, 5, 6, 0, 0, 0}, /* 0x3B (00111011) */
{3, 4, 5, 6, 0, 0, 0, 0}, /* 0x3C (00111100) */
{1, 3, 4, 5, 6, 0, 0, 0}, /* 0x3D (00111101) */
{2, 3, 4, 5, 6, 0, 0, 0}, /* 0x3E (00111110) */
{1, 2, 3, 4, 5, 6, 0, 0}, /* 0x3F (00111111) */
{7, 0, 0, 0, 0, 0, 0, 0}, /* 0x40 (01000000) */
{1, 7, 0, 0, 0, 0, 0, 0}, /* 0x41 (01000001) */
{2, 7, 0, 0, 0, 0, 0, 0}, /* 0x42 (01000010) */
{1, 2, 7, 0, 0, 0, 0, 0}, /* 0x43 (01000011) */
{3, 7, 0, 0, 0, 0, 0, 0}, /* 0x44 (01000100) */
{1, 3, 7, 0, 0, 0, 0, 0}, /* 0x45 (01000101) */
{2, 3, 7, 0, 0, 0, 0, 0}, /* 0x46 (01000110) */
{1, 2, 3, 7, 0, 0, 0, 0}, /* 0x47 (01000111) */
{4, 7, 0, 0, 0, 0, 0, 0}, /* 0x48 (01001000) */
{1, 4, 7, 0, 0, 0, 0, 0}, /* 0x49 (01001001) */
{2, 4, 7, 0, 0, 0, 0, 0}, /* 0x4A (01001010) */
{1, 2, 4, 7, 0, 0, 0, 0}, /* 0x4B (01001011) */
{3, 4, 7, 0, 0, 0, 0, 0}, /* 0x4C (01001100) */
{1, 3, 4, 7, 0, 0, 0, 0}, /* 0x4D (01001101) */
{2, 3, 4, 7, 0, 0, 0, 0}, /* 0x4E (01001110) */
{1, 2, 3, 4, 7, 0, 0, 0}, /* 0x4F (01001111) */
{5, 7, 0, 0, 0, 0, 0, 0}, /* 0x50 (01010000) */
{1, 5, 7, 0, 0, 0, 0, 0}, /* 0x51 (01010001) */
{2, 5, 7, 0, 0, 0, 0, 0}, /* 0x52 (01010010) */
{1, 2, 5, 7, 0, 0, 0, 0}, /* 0x53 (01010011) */
{3, 5, 7, 0, 0, 0, 0, 0}, /* 0x54 (01010100) */
{1, 3, 5, 7, 0, 0, 0, 0}, /* 0x55 (01010101) */
{2, 3, 5, 7, 0, 0, 0, 0}, /* 0x56 (01010110) */
{1, 2, 3, 5, 7, 0, 0, 0}, /* 0x57 (01010111) */
{4, 5, 7, 0, 0, 0, 0, 0}, /* 0x58 (01011000) */
{1, 4, 5, 7, 0, 0, 0, 0}, /* 0x59 (01011001) */
{2, 4, 5, 7, 0, 0, 0, 0}, /* 0x5A (01011010) */
{1, 2, 4, 5, 7, 0, 0, 0}, /* 0x5B (01011011) */
{3, 4, 5, 7, 0, 0, 0, 0}, /* 0x5C (01011100) */
{1, 3, 4, 5, 7, 0, 0, 0}, /* 0x5D (01011101) */
{2, 3, 4, 5, 7, 0, 0, 0}, /* 0x5E (01011110) */
{1, 2, 3, 4, 5, 7, 0, 0}, /* 0x5F (01011111) */
{6, 7, 0, 0, 0, 0, 0, 0}, /* 0x60 (01100000) */
{1, 6, 7, 0, 0, 0, 0, 0}, /* 0x61 (01100001) */
{2, 6, 7, 0, 0, 0, 0, 0}, /* 0x62 (01100010) */
{1, 2, 6, 7, 0, 0, 0, 0}, /* 0x63 (01100011) */
{3, 6, 7, 0, 0, 0, 0, 0}, /* 0x64 (01100100) */
{1, 3, 6, 7, 0, 0, 0, 0}, /* 0x65 (01100101) */
{2, 3, 6, 7, 0, 0, 0, 0}, /* 0x66 (01100110) */
{1, 2, 3, 6, 7, 0, 0, 0}, /* 0x67 (01100111) */
{4, 6, 7, 0, 0, 0, 0, 0}, /* 0x68 (01101000) */
{1, 4, 6, 7, 0, 0, 0, 0}, /* 0x69 (01101001) */
{2, 4, 6, 7, 0, 0, 0, 0}, /* 0x6A (01101010) */
{1, 2, 4, 6, 7, 0, 0, 0}, /* 0x6B (01101011) */
{3, 4, 6, 7, 0, 0, 0, 0}, /* 0x6C (01101100) */
{1, 3, 4, 6, 7, 0, 0, 0}, /* 0x6D (01101101) */
{2, 3, 4, 6, 7, 0, 0, 0}, /* 0x6E (01101110) */
{1, 2, 3, 4, 6, 7, 0, 0}, /* 0x6F (01101111) */
{5, 6, 7, 0, 0, 0, 0, 0}, /* 0x70 (01110000) */
{1, 5, 6, 7, 0, 0, 0, 0}, /* 0x71 (01110001) */
{2, 5, 6, 7, 0, 0, 0, 0}, /* 0x72 (01110010) */
{1, 2, 5, 6, 7, 0, 0, 0}, /* 0x73 (01110011) */
{3, 5, 6, 7, 0, 0, 0, 0}, /* 0x74 (01110100) */
{1, 3, 5, 6, 7, 0, 0, 0}, /* 0x75 (01110101) */
{2, 3, 5, 6, 7, 0, 0, 0}, /* 0x76 (01110110) */
{1, 2, 3, 5, 6, 7, 0, 0}, /* 0x77 (01110111) */
{4, 5, 6, 7, 0, 0, 0, 0}, /* 0x78 (01111000) */
{1, 4, 5, 6, 7, 0, 0, 0}, /* 0x79 (01111001) */
{2, 4, 5, 6, 7, 0, 0, 0}, /* 0x7A (01111010) */
{1, 2, 4, 5, 6, 7, 0, 0}, /* 0x7B (01111011) */
{3, 4, 5, 6, 7, 0, 0, 0}, /* 0x7C (01111100) */
{1, 3, 4, 5, 6, 7, 0, 0}, /* 0x7D (01111101) */
{2, 3, 4, 5, 6, 7, 0, 0}, /* 0x7E (01111110) */
{1, 2, 3, 4, 5, 6, 7, 0}, /* 0x7F (01111111) */
{8, 0, 0, 0, 0, 0, 0, 0}, /* 0x80 (10000000) */
{1, 8, 0, 0, 0, 0, 0, 0}, /* 0x81 (10000001) */
{2, 8, 0, 0, 0, 0, 0, 0}, /* 0x82 (10000010) */
{1, 2, 8, 0, 0, 0, 0, 0}, /* 0x83 (10000011) */
{3, 8, 0, 0, 0, 0, 0, 0}, /* 0x84 (10000100) */
{1, 3, 8, 0, 0, 0, 0, 0}, /* 0x85 (10000101) */
{2, 3, 8, 0, 0, 0, 0, 0}, /* 0x86 (10000110) */
{1, 2, 3, 8, 0, 0, 0, 0}, /* 0x87 (10000111) */
{4, 8, 0, 0, 0, 0, 0, 0}, /* 0x88 (10001000) */
{1, 4, 8, 0, 0, 0, 0, 0}, /* 0x89 (10001001) */
{2, 4, 8, 0, 0, 0, 0, 0}, /* 0x8A (10001010) */
{1, 2, 4, 8, 0, 0, 0, 0}, /* 0x8B (10001011) */
{3, 4, 8, 0, 0, 0, 0, 0}, /* 0x8C (10001100) */
{1, 3, 4, 8, 0, 0, 0, 0}, /* 0x8D (10001101) */
{2, 3, 4, 8, 0, 0, 0, 0}, /* 0x8E (10001110) */
{1, 2, 3, 4, 8, 0, 0, 0}, /* 0x8F (10001111) */
{5, 8, 0, 0, 0, 0, 0, 0}, /* 0x90 (10010000) */
{1, 5, 8, 0, 0, 0, 0, 0}, /* 0x91 (10010001) */
{2, 5, 8, 0, 0, 0, 0, 0}, /* 0x92 (10010010) */
{1, 2, 5, 8, 0, 0, 0, 0}, /* 0x93 (10010011) */
{3, 5, 8, 0, 0, 0, 0, 0}, /* 0x94 (10010100) */
{1, 3, 5, 8, 0, 0, 0, 0}, /* 0x95 (10010101) */
{2, 3, 5, 8, 0, 0, 0, 0}, /* 0x96 (10010110) */
{1, 2, 3, 5, 8, 0, 0, 0}, /* 0x97 (10010111) */
{4, 5, 8, 0, 0, 0, 0, 0}, /* 0x98 (10011000) */
{1, 4, 5, 8, 0, 0, 0, 0}, /* 0x99 (10011001) */
{2, 4, 5, 8, 0, 0, 0, 0}, /* 0x9A (10011010) */
{1, 2, 4, 5, 8, 0, 0, 0}, /* 0x9B (10011011) */
{3, 4, 5, 8, 0, 0, 0, 0}, /* 0x9C (10011100) */
{1, 3, 4, 5, 8, 0, 0, 0}, /* 0x9D (10011101) */
{2, 3, 4, 5, 8, 0, 0, 0}, /* 0x9E (10011110) */
{1, 2, 3, 4, 5, 8, 0, 0}, /* 0x9F (10011111) */
{6, 8, 0, 0, 0, 0, 0, 0}, /* 0xA0 (10100000) */
{1, 6, 8, 0, 0, 0, 0, 0}, /* 0xA1 (10100001) */
{2, 6, 8, 0, 0, 0, 0, 0}, /* 0xA2 (10100010) */
{1, 2, 6, 8, 0, 0, 0, 0}, /* 0xA3 (10100011) */
{3, 6, 8, 0, 0, 0, 0, 0}, /* 0xA4 (10100100) */
{1, 3, 6, 8, 0, 0, 0, 0}, /* 0xA5 (10100101) */
{2, 3, 6, 8, 0, 0, 0, 0}, /* 0xA6 (10100110) */
{1, 2, 3, 6, 8, 0, 0, 0}, /* 0xA7 (10100111) */
{4, 6, 8, 0, 0, 0, 0, 0}, /* 0xA8 (10101000) */
{1, 4, 6, 8, 0, 0, 0, 0}, /* 0xA9 (10101001) */
{2, 4, 6, 8, 0, 0, 0, 0}, /* 0xAA (10101010) */
{1, 2, 4, 6, 8, 0, 0, 0}, /* 0xAB (10101011) */
{3, 4, 6, 8, 0, 0, 0, 0}, /* 0xAC (10101100) */
{1, 3, 4, 6, 8, 0, 0, 0}, /* 0xAD (10101101) */
{2, 3, 4, 6, 8, 0, 0, 0}, /* 0xAE (10101110) */
{1, 2, 3, 4, 6, 8, 0, 0}, /* 0xAF (10101111) */
{5, 6, 8, 0, 0, 0, 0, 0}, /* 0xB0 (10110000) */
{1, 5, 6, 8, 0, 0, 0, 0}, /* 0xB1 (10110001) */
{2, 5, 6, 8, 0, 0, 0, 0}, /* 0xB2 (10110010) */
{1, 2, 5, 6, 8, 0, 0, 0}, /* 0xB3 (10110011) */
{3, 5, 6, 8, 0, 0, 0, 0}, /* 0xB4 (10110100) */
{1, 3, 5, 6, 8, 0, 0, 0}, /* 0xB5 (10110101) */
{2, 3, 5, 6, 8, 0, 0, 0}, /* 0xB6 (10110110) */
{1, 2, 3, 5, 6, 8, 0, 0}, /* 0xB7 (10110111) */
{4, 5, 6, 8, 0, 0, 0, 0}, /* 0xB8 (10111000) */
{1, 4, 5, 6, 8, 0, 0, 0}, /* 0xB9 (10111001) */
{2, 4, 5, 6, 8, 0, 0, 0}, /* 0xBA (10111010) */
{1, 2, 4, 5, 6, 8, 0, 0}, /* 0xBB (10111011) */
{3, 4, 5, 6, 8, 0, 0, 0}, /* 0xBC (10111100) */
{1, 3, 4, 5, 6, 8, 0, 0}, /* 0xBD (10111101) */
{2, 3, 4, 5, 6, 8, 0, 0}, /* 0xBE (10111110) */
{1, 2, 3, 4, 5, 6, 8, 0}, /* 0xBF (10111111) */
{7, 8, 0, 0, 0, 0, 0, 0}, /* 0xC0 (11000000) */
{1, 7, 8, 0, 0, 0, 0, 0}, /* 0xC1 (11000001) */
{2, 7, 8, 0, 0, 0, 0, 0}, /* 0xC2 (11000010) */
{1, 2, 7, 8, 0, 0, 0, 0}, /* 0xC3 (11000011) */
{3, 7, 8, 0, 0, 0, 0, 0}, /* 0xC4 (11000100) */
{1, 3, 7, 8, 0, 0, 0, 0}, /* 0xC5 (11000101) */
{2, 3, 7, 8, 0, 0, 0, 0}, /* 0xC6 (11000110) */
{1, 2, 3, 7, 8, 0, 0, 0}, /* 0xC7 (11000111) */
{4, 7, 8, 0, 0, 0, 0, 0}, /* 0xC8 (11001000) */
{1, 4, 7, 8, 0, 0, 0, 0}, /* 0xC9 (11001001) */
{2, 4, 7, 8, 0, 0, 0, 0}, /* 0xCA (11001010) */
{1, 2, 4, 7, 8, 0, 0, 0}, /* 0xCB (11001011) */
{3, 4, 7, 8, 0, 0, 0, 0}, /* 0xCC (11001100) */
{1, 3, 4, 7, 8, 0, 0, 0}, /* 0xCD (11001101) */
{2, 3, 4, 7, 8, 0, 0, 0}, /* 0xCE (11001110) */
{1, 2, 3, 4, 7, 8, 0, 0}, /* 0xCF (11001111) */
{5, 7, 8, 0, 0, 0, 0, 0}, /* 0xD0 (11010000) */
{1, 5, 7, 8, 0, 0, 0, 0}, /* 0xD1 (11010001) */
{2, 5, 7, 8, 0, 0, 0, 0}, /* 0xD2 (11010010) */
{1, 2, 5, 7, 8, 0, 0, 0}, /* 0xD3 (11010011) */
{3, 5, 7, 8, 0, 0, 0, 0}, /* 0xD4 (11010100) */
{1, 3, 5, 7, 8, 0, 0, 0}, /* 0xD5 (11010101) */
{2, 3, 5, 7, 8, 0, 0, 0}, /* 0xD6 (11010110) */
{1, 2, 3, 5, 7, 8, 0, 0}, /* 0xD7 (11010111) */
{4, 5, 7, 8, 0, 0, 0, 0}, /* 0xD8 (11011000) */
{1, 4, 5, 7, 8, 0, 0, 0}, /* 0xD9 (11011001) */
{2, 4, 5, 7, 8, 0, 0, 0}, /* 0xDA (11011010) */
{1, 2, 4, 5, 7, 8, 0, 0}, /* 0xDB (11011011) */
{3, 4, 5, 7, 8, 0, 0, 0}, /* 0xDC (11011100) */
{1, 3, 4, 5, 7, 8, 0, 0}, /* 0xDD (11011101) */
{2, 3, 4, 5, 7, 8, 0, 0}, /* 0xDE (11011110) */
{1, 2, 3, 4, 5, 7, 8, 0}, /* 0xDF (11011111) */
{6, 7, 8, 0, 0, 0, 0, 0}, /* 0xE0 (11100000) */
{1, 6, 7, 8, 0, 0, 0, 0}, /* 0xE1 (11100001) */
{2, 6, 7, 8, 0, 0, 0, 0}, /* 0xE2 (11100010) */
{1, 2, 6, 7, 8, 0, 0, 0}, /* 0xE3 (11100011) */
{3, 6, 7, 8, 0, 0, 0, 0}, /* 0xE4 (11100100) */
{1, 3, 6, 7, 8, 0, 0, 0}, /* 0xE5 (11100101) */
{2, 3, 6, 7, 8, 0, 0, 0}, /* 0xE6 (11100110) */
{1, 2, 3, 6, 7, 8, 0, 0}, /* 0xE7 (11100111) */
{4, 6, 7, 8, 0, 0, 0, 0}, /* 0xE8 (11101000) */
{1, 4, 6, 7, 8, 0, 0, 0}, /* 0xE9 (11101001) */
{2, 4, 6, 7, 8, 0, 0, 0}, /* 0xEA (11101010) */
{1, 2, 4, 6, 7, 8, 0, 0}, /* 0xEB (11101011) */
{3, 4, 6, 7, 8, 0, 0, 0}, /* 0xEC (11101100) */
{1, 3, 4, 6, 7, 8, 0, 0}, /* 0xED (11101101) */
{2, 3, 4, 6, 7, 8, 0, 0}, /* 0xEE (11101110) */
{1, 2, 3, 4, 6, 7, 8, 0}, /* 0xEF (11101111) */
{5, 6, 7, 8, 0, 0, 0, 0}, /* 0xF0 (11110000) */
{1, 5, 6, 7, 8, 0, 0, 0}, /* 0xF1 (11110001) */
{2, 5, 6, 7, 8, 0, 0, 0}, /* 0xF2 (11110010) */
{1, 2, 5, 6, 7, 8, 0, 0}, /* 0xF3 (11110011) */
{3, 5, 6, 7, 8, 0, 0, 0}, /* 0xF4 (11110100) */
{1, 3, 5, 6, 7, 8, 0, 0}, /* 0xF5 (11110101) */
{2, 3, 5, 6, 7, 8, 0, 0}, /* 0xF6 (11110110) */
{1, 2, 3, 5, 6, 7, 8, 0}, /* 0xF7 (11110111) */
{4, 5, 6, 7, 8, 0, 0, 0}, /* 0xF8 (11111000) */
{1, 4, 5, 6, 7, 8, 0, 0}, /* 0xF9 (11111001) */
{2, 4, 5, 6, 7, 8, 0, 0}, /* 0xFA (11111010) */
{1, 2, 4, 5, 6, 7, 8, 0}, /* 0xFB (11111011) */
{3, 4, 5, 6, 7, 8, 0, 0}, /* 0xFC (11111100) */
{1, 3, 4, 5, 6, 7, 8, 0}, /* 0xFD (11111101) */
{2, 3, 4, 5, 6, 7, 8, 0}, /* 0xFE (11111110) */
{1, 2, 3, 4, 5, 6, 7, 8} /* 0xFF (11111111) */
};
#endif // #if CROARING_IS_X64
#if CROARING_IS_X64
// same as vecDecodeTable but in 16 bits
ALIGNED(32)
static uint16_t vecDecodeTable_uint16[256][8] = {
{0, 0, 0, 0, 0, 0, 0, 0}, /* 0x00 (00000000) */
{1, 0, 0, 0, 0, 0, 0, 0}, /* 0x01 (00000001) */
{2, 0, 0, 0, 0, 0, 0, 0}, /* 0x02 (00000010) */
{1, 2, 0, 0, 0, 0, 0, 0}, /* 0x03 (00000011) */
{3, 0, 0, 0, 0, 0, 0, 0}, /* 0x04 (00000100) */
{1, 3, 0, 0, 0, 0, 0, 0}, /* 0x05 (00000101) */
{2, 3, 0, 0, 0, 0, 0, 0}, /* 0x06 (00000110) */
{1, 2, 3, 0, 0, 0, 0, 0}, /* 0x07 (00000111) */
{4, 0, 0, 0, 0, 0, 0, 0}, /* 0x08 (00001000) */
{1, 4, 0, 0, 0, 0, 0, 0}, /* 0x09 (00001001) */
{2, 4, 0, 0, 0, 0, 0, 0}, /* 0x0A (00001010) */
{1, 2, 4, 0, 0, 0, 0, 0}, /* 0x0B (00001011) */
{3, 4, 0, 0, 0, 0, 0, 0}, /* 0x0C (00001100) */
{1, 3, 4, 0, 0, 0, 0, 0}, /* 0x0D (00001101) */
{2, 3, 4, 0, 0, 0, 0, 0}, /* 0x0E (00001110) */
{1, 2, 3, 4, 0, 0, 0, 0}, /* 0x0F (00001111) */
{5, 0, 0, 0, 0, 0, 0, 0}, /* 0x10 (00010000) */
{1, 5, 0, 0, 0, 0, 0, 0}, /* 0x11 (00010001) */
{2, 5, 0, 0, 0, 0, 0, 0}, /* 0x12 (00010010) */
{1, 2, 5, 0, 0, 0, 0, 0}, /* 0x13 (00010011) */
{3, 5, 0, 0, 0, 0, 0, 0}, /* 0x14 (00010100) */
{1, 3, 5, 0, 0, 0, 0, 0}, /* 0x15 (00010101) */
{2, 3, 5, 0, 0, 0, 0, 0}, /* 0x16 (00010110) */
{1, 2, 3, 5, 0, 0, 0, 0}, /* 0x17 (00010111) */
{4, 5, 0, 0, 0, 0, 0, 0}, /* 0x18 (00011000) */
{1, 4, 5, 0, 0, 0, 0, 0}, /* 0x19 (00011001) */
{2, 4, 5, 0, 0, 0, 0, 0}, /* 0x1A (00011010) */
{1, 2, 4, 5, 0, 0, 0, 0}, /* 0x1B (00011011) */
{3, 4, 5, 0, 0, 0, 0, 0}, /* 0x1C (00011100) */
{1, 3, 4, 5, 0, 0, 0, 0}, /* 0x1D (00011101) */
{2, 3, 4, 5, 0, 0, 0, 0}, /* 0x1E (00011110) */
{1, 2, 3, 4, 5, 0, 0, 0}, /* 0x1F (00011111) */
{6, 0, 0, 0, 0, 0, 0, 0}, /* 0x20 (00100000) */
{1, 6, 0, 0, 0, 0, 0, 0}, /* 0x21 (00100001) */
{2, 6, 0, 0, 0, 0, 0, 0}, /* 0x22 (00100010) */
{1, 2, 6, 0, 0, 0, 0, 0}, /* 0x23 (00100011) */
{3, 6, 0, 0, 0, 0, 0, 0}, /* 0x24 (00100100) */
{1, 3, 6, 0, 0, 0, 0, 0}, /* 0x25 (00100101) */
{2, 3, 6, 0, 0, 0, 0, 0}, /* 0x26 (00100110) */
{1, 2, 3, 6, 0, 0, 0, 0}, /* 0x27 (00100111) */
{4, 6, 0, 0, 0, 0, 0, 0}, /* 0x28 (00101000) */
{1, 4, 6, 0, 0, 0, 0, 0}, /* 0x29 (00101001) */
{2, 4, 6, 0, 0, 0, 0, 0}, /* 0x2A (00101010) */
{1, 2, 4, 6, 0, 0, 0, 0}, /* 0x2B (00101011) */
{3, 4, 6, 0, 0, 0, 0, 0}, /* 0x2C (00101100) */
{1, 3, 4, 6, 0, 0, 0, 0}, /* 0x2D (00101101) */
{2, 3, 4, 6, 0, 0, 0, 0}, /* 0x2E (00101110) */
{1, 2, 3, 4, 6, 0, 0, 0}, /* 0x2F (00101111) */
{5, 6, 0, 0, 0, 0, 0, 0}, /* 0x30 (00110000) */
{1, 5, 6, 0, 0, 0, 0, 0}, /* 0x31 (00110001) */
{2, 5, 6, 0, 0, 0, 0, 0}, /* 0x32 (00110010) */
{1, 2, 5, 6, 0, 0, 0, 0}, /* 0x33 (00110011) */
{3, 5, 6, 0, 0, 0, 0, 0}, /* 0x34 (00110100) */
{1, 3, 5, 6, 0, 0, 0, 0}, /* 0x35 (00110101) */
{2, 3, 5, 6, 0, 0, 0, 0}, /* 0x36 (00110110) */
{1, 2, 3, 5, 6, 0, 0, 0}, /* 0x37 (00110111) */
{4, 5, 6, 0, 0, 0, 0, 0}, /* 0x38 (00111000) */
{1, 4, 5, 6, 0, 0, 0, 0}, /* 0x39 (00111001) */
{2, 4, 5, 6, 0, 0, 0, 0}, /* 0x3A (00111010) */
{1, 2, 4, 5, 6, 0, 0, 0}, /* 0x3B (00111011) */
{3, 4, 5, 6, 0, 0, 0, 0}, /* 0x3C (00111100) */
{1, 3, 4, 5, 6, 0, 0, 0}, /* 0x3D (00111101) */
{2, 3, 4, 5, 6, 0, 0, 0}, /* 0x3E (00111110) */
{1, 2, 3, 4, 5, 6, 0, 0}, /* 0x3F (00111111) */
{7, 0, 0, 0, 0, 0, 0, 0}, /* 0x40 (01000000) */
{1, 7, 0, 0, 0, 0, 0, 0}, /* 0x41 (01000001) */
{2, 7, 0, 0, 0, 0, 0, 0}, /* 0x42 (01000010) */
{1, 2, 7, 0, 0, 0, 0, 0}, /* 0x43 (01000011) */
{3, 7, 0, 0, 0, 0, 0, 0}, /* 0x44 (01000100) */
{1, 3, 7, 0, 0, 0, 0, 0}, /* 0x45 (01000101) */
{2, 3, 7, 0, 0, 0, 0, 0}, /* 0x46 (01000110) */
{1, 2, 3, 7, 0, 0, 0, 0}, /* 0x47 (01000111) */
{4, 7, 0, 0, 0, 0, 0, 0}, /* 0x48 (01001000) */
{1, 4, 7, 0, 0, 0, 0, 0}, /* 0x49 (01001001) */
{2, 4, 7, 0, 0, 0, 0, 0}, /* 0x4A (01001010) */
{1, 2, 4, 7, 0, 0, 0, 0}, /* 0x4B (01001011) */
{3, 4, 7, 0, 0, 0, 0, 0}, /* 0x4C (01001100) */
{1, 3, 4, 7, 0, 0, 0, 0}, /* 0x4D (01001101) */
{2, 3, 4, 7, 0, 0, 0, 0}, /* 0x4E (01001110) */
{1, 2, 3, 4, 7, 0, 0, 0}, /* 0x4F (01001111) */
{5, 7, 0, 0, 0, 0, 0, 0}, /* 0x50 (01010000) */
{1, 5, 7, 0, 0, 0, 0, 0}, /* 0x51 (01010001) */
{2, 5, 7, 0, 0, 0, 0, 0}, /* 0x52 (01010010) */
{1, 2, 5, 7, 0, 0, 0, 0}, /* 0x53 (01010011) */
{3, 5, 7, 0, 0, 0, 0, 0}, /* 0x54 (01010100) */
{1, 3, 5, 7, 0, 0, 0, 0}, /* 0x55 (01010101) */
{2, 3, 5, 7, 0, 0, 0, 0}, /* 0x56 (01010110) */
{1, 2, 3, 5, 7, 0, 0, 0}, /* 0x57 (01010111) */
{4, 5, 7, 0, 0, 0, 0, 0}, /* 0x58 (01011000) */
{1, 4, 5, 7, 0, 0, 0, 0}, /* 0x59 (01011001) */
{2, 4, 5, 7, 0, 0, 0, 0}, /* 0x5A (01011010) */
{1, 2, 4, 5, 7, 0, 0, 0}, /* 0x5B (01011011) */
{3, 4, 5, 7, 0, 0, 0, 0}, /* 0x5C (01011100) */
{1, 3, 4, 5, 7, 0, 0, 0}, /* 0x5D (01011101) */
{2, 3, 4, 5, 7, 0, 0, 0}, /* 0x5E (01011110) */
{1, 2, 3, 4, 5, 7, 0, 0}, /* 0x5F (01011111) */
{6, 7, 0, 0, 0, 0, 0, 0}, /* 0x60 (01100000) */
{1, 6, 7, 0, 0, 0, 0, 0}, /* 0x61 (01100001) */
{2, 6, 7, 0, 0, 0, 0, 0}, /* 0x62 (01100010) */
{1, 2, 6, 7, 0, 0, 0, 0}, /* 0x63 (01100011) */
{3, 6, 7, 0, 0, 0, 0, 0}, /* 0x64 (01100100) */
{1, 3, 6, 7, 0, 0, 0, 0}, /* 0x65 (01100101) */
{2, 3, 6, 7, 0, 0, 0, 0}, /* 0x66 (01100110) */
{1, 2, 3, 6, 7, 0, 0, 0}, /* 0x67 (01100111) */
{4, 6, 7, 0, 0, 0, 0, 0}, /* 0x68 (01101000) */
{1, 4, 6, 7, 0, 0, 0, 0}, /* 0x69 (01101001) */
{2, 4, 6, 7, 0, 0, 0, 0}, /* 0x6A (01101010) */
{1, 2, 4, 6, 7, 0, 0, 0}, /* 0x6B (01101011) */
{3, 4, 6, 7, 0, 0, 0, 0}, /* 0x6C (01101100) */
{1, 3, 4, 6, 7, 0, 0, 0}, /* 0x6D (01101101) */
{2, 3, 4, 6, 7, 0, 0, 0}, /* 0x6E (01101110) */
{1, 2, 3, 4, 6, 7, 0, 0}, /* 0x6F (01101111) */
{5, 6, 7, 0, 0, 0, 0, 0}, /* 0x70 (01110000) */
{1, 5, 6, 7, 0, 0, 0, 0}, /* 0x71 (01110001) */
{2, 5, 6, 7, 0, 0, 0, 0}, /* 0x72 (01110010) */
{1, 2, 5, 6, 7, 0, 0, 0}, /* 0x73 (01110011) */
{3, 5, 6, 7, 0, 0, 0, 0}, /* 0x74 (01110100) */
{1, 3, 5, 6, 7, 0, 0, 0}, /* 0x75 (01110101) */
{2, 3, 5, 6, 7, 0, 0, 0}, /* 0x76 (01110110) */
{1, 2, 3, 5, 6, 7, 0, 0}, /* 0x77 (01110111) */
{4, 5, 6, 7, 0, 0, 0, 0}, /* 0x78 (01111000) */
{1, 4, 5, 6, 7, 0, 0, 0}, /* 0x79 (01111001) */
{2, 4, 5, 6, 7, 0, 0, 0}, /* 0x7A (01111010) */
{1, 2, 4, 5, 6, 7, 0, 0}, /* 0x7B (01111011) */
{3, 4, 5, 6, 7, 0, 0, 0}, /* 0x7C (01111100) */
{1, 3, 4, 5, 6, 7, 0, 0}, /* 0x7D (01111101) */
{2, 3, 4, 5, 6, 7, 0, 0}, /* 0x7E (01111110) */
{1, 2, 3, 4, 5, 6, 7, 0}, /* 0x7F (01111111) */
{8, 0, 0, 0, 0, 0, 0, 0}, /* 0x80 (10000000) */
{1, 8, 0, 0, 0, 0, 0, 0}, /* 0x81 (10000001) */
{2, 8, 0, 0, 0, 0, 0, 0}, /* 0x82 (10000010) */
{1, 2, 8, 0, 0, 0, 0, 0}, /* 0x83 (10000011) */
{3, 8, 0, 0, 0, 0, 0, 0}, /* 0x84 (10000100) */
{1, 3, 8, 0, 0, 0, 0, 0}, /* 0x85 (10000101) */
{2, 3, 8, 0, 0, 0, 0, 0}, /* 0x86 (10000110) */
{1, 2, 3, 8, 0, 0, 0, 0}, /* 0x87 (10000111) */
{4, 8, 0, 0, 0, 0, 0, 0}, /* 0x88 (10001000) */
{1, 4, 8, 0, 0, 0, 0, 0}, /* 0x89 (10001001) */
{2, 4, 8, 0, 0, 0, 0, 0}, /* 0x8A (10001010) */
{1, 2, 4, 8, 0, 0, 0, 0}, /* 0x8B (10001011) */
{3, 4, 8, 0, 0, 0, 0, 0}, /* 0x8C (10001100) */
{1, 3, 4, 8, 0, 0, 0, 0}, /* 0x8D (10001101) */
{2, 3, 4, 8, 0, 0, 0, 0}, /* 0x8E (10001110) */
{1, 2, 3, 4, 8, 0, 0, 0}, /* 0x8F (10001111) */
{5, 8, 0, 0, 0, 0, 0, 0}, /* 0x90 (10010000) */
{1, 5, 8, 0, 0, 0, 0, 0}, /* 0x91 (10010001) */
{2, 5, 8, 0, 0, 0, 0, 0}, /* 0x92 (10010010) */
{1, 2, 5, 8, 0, 0, 0, 0}, /* 0x93 (10010011) */
{3, 5, 8, 0, 0, 0, 0, 0}, /* 0x94 (10010100) */
{1, 3, 5, 8, 0, 0, 0, 0}, /* 0x95 (10010101) */
{2, 3, 5, 8, 0, 0, 0, 0}, /* 0x96 (10010110) */
{1, 2, 3, 5, 8, 0, 0, 0}, /* 0x97 (10010111) */
{4, 5, 8, 0, 0, 0, 0, 0}, /* 0x98 (10011000) */
{1, 4, 5, 8, 0, 0, 0, 0}, /* 0x99 (10011001) */
{2, 4, 5, 8, 0, 0, 0, 0}, /* 0x9A (10011010) */
{1, 2, 4, 5, 8, 0, 0, 0}, /* 0x9B (10011011) */
{3, 4, 5, 8, 0, 0, 0, 0}, /* 0x9C (10011100) */
{1, 3, 4, 5, 8, 0, 0, 0}, /* 0x9D (10011101) */
{2, 3, 4, 5, 8, 0, 0, 0}, /* 0x9E (10011110) */
{1, 2, 3, 4, 5, 8, 0, 0}, /* 0x9F (10011111) */
{6, 8, 0, 0, 0, 0, 0, 0}, /* 0xA0 (10100000) */
{1, 6, 8, 0, 0, 0, 0, 0}, /* 0xA1 (10100001) */
{2, 6, 8, 0, 0, 0, 0, 0}, /* 0xA2 (10100010) */
{1, 2, 6, 8, 0, 0, 0, 0}, /* 0xA3 (10100011) */
{3, 6, 8, 0, 0, 0, 0, 0}, /* 0xA4 (10100100) */
{1, 3, 6, 8, 0, 0, 0, 0}, /* 0xA5 (10100101) */
{2, 3, 6, 8, 0, 0, 0, 0}, /* 0xA6 (10100110) */
{1, 2, 3, 6, 8, 0, 0, 0}, /* 0xA7 (10100111) */
{4, 6, 8, 0, 0, 0, 0, 0}, /* 0xA8 (10101000) */
{1, 4, 6, 8, 0, 0, 0, 0}, /* 0xA9 (10101001) */
{2, 4, 6, 8, 0, 0, 0, 0}, /* 0xAA (10101010) */
{1, 2, 4, 6, 8, 0, 0, 0}, /* 0xAB (10101011) */
{3, 4, 6, 8, 0, 0, 0, 0}, /* 0xAC (10101100) */
{1, 3, 4, 6, 8, 0, 0, 0}, /* 0xAD (10101101) */
{2, 3, 4, 6, 8, 0, 0, 0}, /* 0xAE (10101110) */
{1, 2, 3, 4, 6, 8, 0, 0}, /* 0xAF (10101111) */
{5, 6, 8, 0, 0, 0, 0, 0}, /* 0xB0 (10110000) */
{1, 5, 6, 8, 0, 0, 0, 0}, /* 0xB1 (10110001) */
{2, 5, 6, 8, 0, 0, 0, 0}, /* 0xB2 (10110010) */
{1, 2, 5, 6, 8, 0, 0, 0}, /* 0xB3 (10110011) */
{3, 5, 6, 8, 0, 0, 0, 0}, /* 0xB4 (10110100) */
{1, 3, 5, 6, 8, 0, 0, 0}, /* 0xB5 (10110101) */
{2, 3, 5, 6, 8, 0, 0, 0}, /* 0xB6 (10110110) */
{1, 2, 3, 5, 6, 8, 0, 0}, /* 0xB7 (10110111) */
{4, 5, 6, 8, 0, 0, 0, 0}, /* 0xB8 (10111000) */
{1, 4, 5, 6, 8, 0, 0, 0}, /* 0xB9 (10111001) */
{2, 4, 5, 6, 8, 0, 0, 0}, /* 0xBA (10111010) */
{1, 2, 4, 5, 6, 8, 0, 0}, /* 0xBB (10111011) */
{3, 4, 5, 6, 8, 0, 0, 0}, /* 0xBC (10111100) */
{1, 3, 4, 5, 6, 8, 0, 0}, /* 0xBD (10111101) */
{2, 3, 4, 5, 6, 8, 0, 0}, /* 0xBE (10111110) */
{1, 2, 3, 4, 5, 6, 8, 0}, /* 0xBF (10111111) */
{7, 8, 0, 0, 0, 0, 0, 0}, /* 0xC0 (11000000) */
{1, 7, 8, 0, 0, 0, 0, 0}, /* 0xC1 (11000001) */
{2, 7, 8, 0, 0, 0, 0, 0}, /* 0xC2 (11000010) */
{1, 2, 7, 8, 0, 0, 0, 0}, /* 0xC3 (11000011) */
{3, 7, 8, 0, 0, 0, 0, 0}, /* 0xC4 (11000100) */
{1, 3, 7, 8, 0, 0, 0, 0}, /* 0xC5 (11000101) */
{2, 3, 7, 8, 0, 0, 0, 0}, /* 0xC6 (11000110) */
{1, 2, 3, 7, 8, 0, 0, 0}, /* 0xC7 (11000111) */
{4, 7, 8, 0, 0, 0, 0, 0}, /* 0xC8 (11001000) */
{1, 4, 7, 8, 0, 0, 0, 0}, /* 0xC9 (11001001) */
{2, 4, 7, 8, 0, 0, 0, 0}, /* 0xCA (11001010) */
{1, 2, 4, 7, 8, 0, 0, 0}, /* 0xCB (11001011) */
{3, 4, 7, 8, 0, 0, 0, 0}, /* 0xCC (11001100) */
{1, 3, 4, 7, 8, 0, 0, 0}, /* 0xCD (11001101) */
{2, 3, 4, 7, 8, 0, 0, 0}, /* 0xCE (11001110) */
{1, 2, 3, 4, 7, 8, 0, 0}, /* 0xCF (11001111) */
{5, 7, 8, 0, 0, 0, 0, 0}, /* 0xD0 (11010000) */
{1, 5, 7, 8, 0, 0, 0, 0}, /* 0xD1 (11010001) */
{2, 5, 7, 8, 0, 0, 0, 0}, /* 0xD2 (11010010) */
{1, 2, 5, 7, 8, 0, 0, 0}, /* 0xD3 (11010011) */
{3, 5, 7, 8, 0, 0, 0, 0}, /* 0xD4 (11010100) */
{1, 3, 5, 7, 8, 0, 0, 0}, /* 0xD5 (11010101) */
{2, 3, 5, 7, 8, 0, 0, 0}, /* 0xD6 (11010110) */
{1, 2, 3, 5, 7, 8, 0, 0}, /* 0xD7 (11010111) */
{4, 5, 7, 8, 0, 0, 0, 0}, /* 0xD8 (11011000) */
{1, 4, 5, 7, 8, 0, 0, 0}, /* 0xD9 (11011001) */
{2, 4, 5, 7, 8, 0, 0, 0}, /* 0xDA (11011010) */
{1, 2, 4, 5, 7, 8, 0, 0}, /* 0xDB (11011011) */
{3, 4, 5, 7, 8, 0, 0, 0}, /* 0xDC (11011100) */
{1, 3, 4, 5, 7, 8, 0, 0}, /* 0xDD (11011101) */
{2, 3, 4, 5, 7, 8, 0, 0}, /* 0xDE (11011110) */
{1, 2, 3, 4, 5, 7, 8, 0}, /* 0xDF (11011111) */
{6, 7, 8, 0, 0, 0, 0, 0}, /* 0xE0 (11100000) */
{1, 6, 7, 8, 0, 0, 0, 0}, /* 0xE1 (11100001) */
{2, 6, 7, 8, 0, 0, 0, 0}, /* 0xE2 (11100010) */
{1, 2, 6, 7, 8, 0, 0, 0}, /* 0xE3 (11100011) */
{3, 6, 7, 8, 0, 0, 0, 0}, /* 0xE4 (11100100) */
{1, 3, 6, 7, 8, 0, 0, 0}, /* 0xE5 (11100101) */
{2, 3, 6, 7, 8, 0, 0, 0}, /* 0xE6 (11100110) */
{1, 2, 3, 6, 7, 8, 0, 0}, /* 0xE7 (11100111) */
{4, 6, 7, 8, 0, 0, 0, 0}, /* 0xE8 (11101000) */
{1, 4, 6, 7, 8, 0, 0, 0}, /* 0xE9 (11101001) */
{2, 4, 6, 7, 8, 0, 0, 0}, /* 0xEA (11101010) */
{1, 2, 4, 6, 7, 8, 0, 0}, /* 0xEB (11101011) */
{3, 4, 6, 7, 8, 0, 0, 0}, /* 0xEC (11101100) */
{1, 3, 4, 6, 7, 8, 0, 0}, /* 0xED (11101101) */
{2, 3, 4, 6, 7, 8, 0, 0}, /* 0xEE (11101110) */
{1, 2, 3, 4, 6, 7, 8, 0}, /* 0xEF (11101111) */
{5, 6, 7, 8, 0, 0, 0, 0}, /* 0xF0 (11110000) */
{1, 5, 6, 7, 8, 0, 0, 0}, /* 0xF1 (11110001) */
{2, 5, 6, 7, 8, 0, 0, 0}, /* 0xF2 (11110010) */
{1, 2, 5, 6, 7, 8, 0, 0}, /* 0xF3 (11110011) */
{3, 5, 6, 7, 8, 0, 0, 0}, /* 0xF4 (11110100) */
{1, 3, 5, 6, 7, 8, 0, 0}, /* 0xF5 (11110101) */
{2, 3, 5, 6, 7, 8, 0, 0}, /* 0xF6 (11110110) */
{1, 2, 3, 5, 6, 7, 8, 0}, /* 0xF7 (11110111) */
{4, 5, 6, 7, 8, 0, 0, 0}, /* 0xF8 (11111000) */
{1, 4, 5, 6, 7, 8, 0, 0}, /* 0xF9 (11111001) */
{2, 4, 5, 6, 7, 8, 0, 0}, /* 0xFA (11111010) */
{1, 2, 4, 5, 6, 7, 8, 0}, /* 0xFB (11111011) */
{3, 4, 5, 6, 7, 8, 0, 0}, /* 0xFC (11111100) */
{1, 3, 4, 5, 6, 7, 8, 0}, /* 0xFD (11111101) */
{2, 3, 4, 5, 6, 7, 8, 0}, /* 0xFE (11111110) */
{1, 2, 3, 4, 5, 6, 7, 8} /* 0xFF (11111111) */
};
#endif
#if CROARING_IS_X64
#if CROARING_COMPILER_SUPPORTS_AVX512
CROARING_TARGET_AVX512
const uint8_t vbmi2_table[64] = {
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63};
// Reference:
// https://lemire.me/blog/2022/05/10/faster-bitset-decoding-using-intel-avx-512/
//
// One VPCOMPRESSB (AVX-512 VBMI2) turns a whole 64-bit word into the (up to
// 64) byte-sized positions of its set bits in a single shot; the positions are
// then widened 16 at a time with VPMOVZXBD and added to a running base vector.
//
// Two details matter for speed. Each block is stored under a mask derived from
// BZHI(-1, popcount), so a store writes exactly the values it produced: the
// caller needs no padding past the values it asked for, and no store bandwidth
// goes to values nobody wants. And only the ceil(popcount/16) blocks that
// carry a value are computed at all -- bitset containers are usually well
// under half full, so the later blocks are almost always skipped.
CROARING_ALLOW_UNALIGNED
size_t bitset_extract_setbits_avx512(const uint64_t *words, size_t length,
uint32_t *vout, size_t outcapacity,
uint32_t base) {
if (outcapacity == 0) return 0;
uint32_t *out = vout;
uint32_t *initout = out;
uint32_t *safeout = out + outcapacity;
// base_v holds the value of bit 0 of the word being decoded.
__m512i base_v = _mm512_set1_epi32((int)base);
const __m512i inc_v = _mm512_set1_epi32(64);
const __m512i index_table = _mm512_loadu_si512(vbmi2_table);
size_t i = 0;
for (; i < length; i++) {
uint64_t v = words[i];
if (v != 0) {
size_t advance = (size_t)roaring_hamming(v);
if (out + advance > safeout) break;
__m512i vec = _mm512_maskz_compress_epi8((__mmask64)v, index_table);
// BZHI(-1, advance): advance is in [1, 64] here, so the shift is
// well defined.
uint64_t bits = ~UINT64_C(0) >> (64 - advance);
_mm512_mask_storeu_epi32(
out, (__mmask16)bits,
_mm512_add_epi32(
base_v, _mm512_cvtepu8_epi32(_mm512_castsi512_si128(vec))));
if (advance > 16) {
_mm512_mask_storeu_epi32(
out + 16, (__mmask16)(bits >> 16),
_mm512_add_epi32(base_v,
_mm512_cvtepu8_epi32(
_mm512_extracti32x4_epi32(vec, 1))));
if (advance > 32) {
_mm512_mask_storeu_epi32(
out + 32, (__mmask16)(bits >> 32),
_mm512_add_epi32(
base_v, _mm512_cvtepu8_epi32(
_mm512_extracti32x4_epi32(vec, 2))));
if (advance > 48) {
_mm512_mask_storeu_epi32(
out + 48, (__mmask16)(bits >> 48),
_mm512_add_epi32(
base_v,
_mm512_cvtepu8_epi32(
_mm512_extracti32x4_epi32(vec, 3))));
}
}
}
out += advance;
}
base_v = _mm512_add_epi32(base_v, inc_v);
}
base += (uint32_t)(i * 64);
for (; (i < length) && (out < safeout); ++i) {
uint64_t w = words[i];
while ((w != 0) && (out < safeout)) {
int r =
roaring_trailing_zeroes(w); // on x64, should compile to TZCNT
uint32_t val = r + base;
memcpy(out, &val,
sizeof(uint32_t)); // should be compiled as a MOV on x64
out++;
w &= (w - 1);
}
base += 64;
}
return out - initout;
}
// Writes the "advance" values of the word "v" to "out", adding them to the
// 16-bit lanes of "base_v".
static inline void avx512_decode_word_uint16(uint64_t v, unsigned advance,
__m512i base_v,
__m512i index_table,
uint16_t *out) {
__m512i vec = _mm512_maskz_compress_epi8((__mmask64)v, index_table);
_mm512_mask_storeu_epi16(
out, (__mmask32)_bzhi_u64(~UINT64_C(0), advance),
_mm512_add_epi16(base_v,
_mm512_cvtepu8_epi16(_mm512_castsi512_si256(vec))));
if (advance > 32) {
_mm512_mask_storeu_epi16(
out + 32, (__mmask32)_bzhi_u64(~UINT64_C(0), advance - 32),
_mm512_add_epi16(base_v, _mm512_cvtepu8_epi16(
_mm512_extracti64x4_epi64(vec, 1))));
}
}
// Same kernel as bitset_extract_setbits_avx512, writing 16-bit values, so the
// blocks hold 32 values instead of 16. It is called by
// array_container_from_bitset, with "capacity" set to the cardinality, on
// sparse input (at most 4096 values), where many words can be zero. How best
// to skip them depends on how many there are:
//
// - Testing each word ("if (v != 0)") is mispredicted about once per value
// when zero and nonzero words alternate, as when about 1000 values are
// spread out: that was up to 2.7x slower than the loops below.
// - From 2048 values (two per word on average), we decode every word without
// testing it: with v == 0, the masked store writes nothing and we advance by
// zero.
// - Below 2048 values, decoding every word wastes time when most are zero, so
// we test eight words at a time and visit only the nonzero ones: a run of
// zero words costs little, and a group of eight words costs about one
// misprediction, when the inner loop exits.
//
// See microbenchmarks/bitset_to_array_bench.cpp. Either way, we stop once
// "capacity" values are written, so that we do not scan the words past the
// last value.
CROARING_ALLOW_UNALIGNED
size_t bitset_extract_setbits_avx512_uint16(const uint64_t *array,
size_t length, uint16_t *vout,
size_t capacity, uint16_t base) {
if (capacity == 0) return 0;
uint16_t *out = vout;
uint16_t *initout = out;
uint16_t *safeout = vout + capacity;
const __m512i index_table = _mm512_loadu_si512(vbmi2_table);
size_t i = 0;
// When "capacity" truncates the output, the loops below stop at the word
// that does not fit, and the scalar loop at the end writes the values that
// do.
if (capacity >= 2048) {
__m512i base_v = _mm512_set1_epi16((short)base);
const __m512i inc_v = _mm512_set1_epi16(64);
// Four words hold at most 256 values: no need to check the capacity
// for each one while there is room for that many.
for (; (i + 4 <= length) && ((size_t)(safeout - out) >= 4 * 64);
i += 4) {
for (size_t j = 0; j < 4; j++) {
uint64_t v = array[i + j];
unsigned advance = (unsigned)roaring_hamming(v);
avx512_decode_word_uint16(v, advance, base_v, index_table, out);
out += advance;
base_v = _mm512_add_epi16(base_v, inc_v);
}
}
for (; (i < length) && (out < safeout); i++) {
uint64_t v = array[i];
unsigned advance = (unsigned)roaring_hamming(v);
if ((size_t)(safeout - out) < advance) break;
avx512_decode_word_uint16(v, advance, base_v, index_table, out);
out += advance;
base_v = _mm512_add_epi16(base_v, inc_v);
}
} else {
bool truncated = false;
while ((i + 8 <= length) && (out < safeout)) {
__m512i words = _mm512_loadu_si512((const __m512i *)(array + i));
uint32_t nonzero = (uint32_t)_mm512_test_epi64_mask(words, words);
while (nonzero != 0) {
size_t j = (size_t)roaring_trailing_zeroes(nonzero);
uint64_t v = array[i + j];
unsigned advance = (unsigned)roaring_hamming(v);
if ((size_t)(safeout - out) < advance) {
i += j;
truncated = true;
break;
}
avx512_decode_word_uint16(
v, advance,
_mm512_set1_epi16((short)(uint16_t)(base + (i + j) * 64)),
index_table, out);
out += advance;
nonzero &= nonzero - 1;
}
if (truncated) break;
i += 8;
}
}
base = (uint16_t)(base + i * 64);
for (; (i < length) && (out < safeout); ++i) {
uint64_t w = array[i];
while ((w != 0) && (out < safeout)) {
int r =
roaring_trailing_zeroes(w); // on x64, should compile to TZCNT
*out = (uint16_t)(r + base);
out++;
w &= (w - 1);
}
base += 64;
}
return out - initout;
}
// Unlike bitset_extract_setbits_avx512_uint16, there is no "if (v != 0)"
// test: on sparse intersections, about half the words are zero and the test
// is mispredicted about once per value. With v == 0, the masked store writes
// nothing and we advance by zero. The stores never write past the last value.
// We stop once all "card" values are written: masked stores with an empty
// mask can still need a slow microcode assist when they touch a page that
// was never written, such as one past the end of "out".
CROARING_ALLOW_UNALIGNED
size_t bitset_extract_intersection_setbits_avx512_uint16(
const uint64_t *__restrict__ words1, const uint64_t *__restrict__ words2,
size_t length, uint16_t *out, size_t card, uint16_t base) {
uint16_t *initout = out;
uint16_t *const endout = out + card;
__m512i base_v = _mm512_set1_epi16((short)base);
const __m512i inc_v = _mm512_set1_epi16(64);
const __m512i index_table = _mm512_loadu_si512(vbmi2_table);
for (size_t i = 0; i < length && out < endout; i++) {
uint64_t v = words1[i] & words2[i];
unsigned advance = (unsigned)roaring_hamming(v);
__m512i vec = _mm512_maskz_compress_epi8((__mmask64)v, index_table);
_mm512_mask_storeu_epi16(
out, (__mmask32)_bzhi_u64(~UINT64_C(0), advance),
_mm512_add_epi16(
base_v, _mm512_cvtepu8_epi16(_mm512_castsi512_si256(vec))));
if (advance > 32) {
_mm512_mask_storeu_epi16(
out + 32, (__mmask32)_bzhi_u64(~UINT64_C(0), advance - 32),
_mm512_add_epi16(
base_v,
_mm512_cvtepu8_epi16(_mm512_extracti64x4_epi64(vec, 1))));
}
out += advance;
base_v = _mm512_add_epi16(base_v, inc_v);
}
return out - initout;
}
CROARING_UNTARGET_AVX512
#endif
CROARING_TARGET_AVX2
CROARING_ALLOW_UNALIGNED
size_t bitset_extract_setbits_avx2(const uint64_t *words, size_t length,
uint32_t *out, size_t outcapacity,
uint32_t base) {
if (outcapacity == 0) return 0;
uint32_t *initout = out;
__m256i baseVec = _mm256_set1_epi32(base - 1);
__m256i incVec = _mm256_set1_epi32(64);
__m256i add8 = _mm256_set1_epi32(8);
uint32_t *safeout = out + outcapacity;
size_t i = 0;
for (; (i < length) && (out + 64 <= safeout); ++i) {
uint64_t w = words[i];
if (w == 0) {
baseVec = _mm256_add_epi32(baseVec, incVec);
} else {
for (int k = 0; k < 4; ++k) {
uint8_t byteA = (uint8_t)w;
uint8_t byteB = (uint8_t)(w >> 8);
w >>= 16;
__m256i vecA =
_mm256_loadu_si256((const __m256i *)vecDecodeTable[byteA]);
__m256i vecB =
_mm256_loadu_si256((const __m256i *)vecDecodeTable[byteB]);
uint8_t advanceA = lengthTable[byteA];
uint8_t advanceB = lengthTable[byteB];
vecA = _mm256_add_epi32(baseVec, vecA);
baseVec = _mm256_add_epi32(baseVec, add8);
vecB = _mm256_add_epi32(baseVec, vecB);
baseVec = _mm256_add_epi32(baseVec, add8);
_mm256_storeu_si256((__m256i *)out, vecA);
out += advanceA;
_mm256_storeu_si256((__m256i *)out, vecB);
out += advanceB;
}
}
}
base += i * 64;
for (; (i < length) && (out < safeout); ++i) {
uint64_t w = words[i];
while ((w != 0) && (out < safeout)) {
int r =
roaring_trailing_zeroes(w); // on x64, should compile to TZCNT
uint32_t val = r + base;
memcpy(out, &val,
sizeof(uint32_t)); // should be compiled as a MOV on x64
out++;
w &= (w - 1);
}
base += 64;
}
return out - initout;
}
CROARING_UNTARGET_AVX2
#endif // CROARING_IS_X64
CROARING_ALLOW_UNALIGNED
size_t bitset_extract_setbits(const uint64_t *words, size_t length,
uint32_t *out, uint32_t base) {
int outpos = 0;
for (size_t i = 0; i < length; ++i) {
uint64_t w = words[i];
while (w != 0) {
int r =
roaring_trailing_zeroes(w); // on x64, should compile to TZCNT
uint32_t val = r + base;
memcpy(out + outpos, &val,
sizeof(uint32_t)); // should be compiled as a MOV on x64
outpos++;
w &= (w - 1);
}
base += 64;
}
return outpos;
}
size_t bitset_extract_intersection_setbits_uint16(
const uint64_t *__restrict__ words1, const uint64_t *__restrict__ words2,
size_t length, uint16_t *out, uint16_t base) {
int outpos = 0;
for (size_t i = 0; i < length; ++i) {
uint64_t w = words1[i] & words2[i];
while (w != 0) {
int r = roaring_trailing_zeroes(w);
out[outpos++] = (uint16_t)(r + base);
w &= (w - 1);
}
base += 64;
}
return outpos;
}
// Decodes the words of (words1 AND words2) from index *i onward, writing K
// values per word unconditionally and advancing only past the real ones, so
// that there is no data-dependent branch unless a word has more than K bits.
// The trailing-zero count of (w | 1 << 63) is that of w when w != 0, and 63
// (a harmless value, later overwritten) when w == 0. The unconditional writes
// can land up to K - 1 values past the last real one, so it stops while 64
// slots of slack remain in "out"; the caller finishes with the plain loop.
#define CROARING_DEFINE_EXTRACT_INTERSECTION_K(K) \
static inline size_t extract_intersection_branchless_##K( \
const uint64_t *__restrict__ words1, \
const uint64_t *__restrict__ words2, size_t length, uint16_t *out, \
size_t card, size_t *i, uint16_t *base) { \
size_t pos = 0; \
size_t j = *i; \
uint16_t b = *base; \
for (; j < length && pos + 64 <= card; ++j) { \
/* Skip groups of four empty words: rare on random data, where */ \
/* the branch is well predicted, but common on clustered data. */ \
if (j + 4 <= length && \
((words1[j] & words2[j]) | (words1[j + 1] & words2[j + 1]) | \
(words1[j + 2] & words2[j + 2]) | \
(words1[j + 3] & words2[j + 3])) == 0) { \
j += 3; \
b = (uint16_t)(b + 256); \
continue; \
} \
uint64_t w = words1[j] & words2[j]; \
for (int k = 0; k < K; k++) { \
out[pos] = (uint16_t)(b + roaring_trailing_zeroes( \
w | (UINT64_C(1) << 63))); \
pos += (w != 0); \
w &= (w - 1); \
} \
while (w != 0) { \
out[pos++] = (uint16_t)(b + roaring_trailing_zeroes(w)); \
w &= (w - 1); \
} \
b = (uint16_t)(b + 64); \
} \
*i = j; \
*base = b; \
return pos; \
}
CROARING_DEFINE_EXTRACT_INTERSECTION_K(1)
CROARING_DEFINE_EXTRACT_INTERSECTION_K(2)
CROARING_DEFINE_EXTRACT_INTERSECTION_K(4)
CROARING_DEFINE_EXTRACT_INTERSECTION_K(8)
#undef CROARING_DEFINE_EXTRACT_INTERSECTION_K
size_t bitset_extract_intersection_setbits_uint16_with_card(
const uint64_t *__restrict__ words1, const uint64_t *__restrict__ words2,
size_t length, uint16_t *out, size_t card, uint16_t base) {
size_t i = 0;
size_t pos;
// Write about 2.5 times as many values per word as the average word
// holds, so that words with more bits than that (handled by a branch)
// are rare. Past 1.6 bits per word, writing 8 values costs more than the
// occasional branch, so 4 values serve up to 3 bits per word. The
// thresholds were measured on an Emerald Rapids Xeon.
if (card * 5 < length * 2) {
pos = extract_intersection_branchless_1(words1, words2, length, out,
card, &i, &base);
} else if (card * 5 < length * 4) {
pos = extract_intersection_branchless_2(words1, words2, length, out,
card, &i, &base);
} else if (card < length * 3) {
pos = extract_intersection_branchless_4(words1, words2, length, out,
card, &i, &base);
} else {
pos = extract_intersection_branchless_8(words1, words2, length, out,
card, &i, &base);
}
return pos + bitset_extract_intersection_setbits_uint16(
words1 + i, words2 + i, length - i, out + pos, base);
}
#if CROARING_IS_X64
/*
* Given a bitset containing "length" 64-bit words, write out the position
* of all the set bits to "out" as 16-bit integers, values start at "base" (can
*be set to zero).
*
* The "out" pointer should be sufficient to store the actual number of bits
*set.
*
* Returns how many values were actually decoded.
*
* This function uses SSE decoding.
*/
CROARING_TARGET_AVX2
CROARING_ALLOW_UNALIGNED
size_t bitset_extract_setbits_sse_uint16(const uint64_t *words, size_t length,
uint16_t *out, size_t outcapacity,
uint16_t base) {
if (outcapacity == 0) return 0;
uint16_t *initout = out;
__m128i baseVec = _mm_set1_epi16(base - 1);
__m128i incVec = _mm_set1_epi16(64);
__m128i add8 = _mm_set1_epi16(8);
uint16_t *safeout = out + outcapacity;
const int numberofbytes = 2; // process two bytes at a time
size_t i = 0;
for (; (i < length) && (out + numberofbytes * 8 <= safeout); ++i) {
uint64_t w = words[i];
if (w == 0) {
baseVec = _mm_add_epi16(baseVec, incVec);
} else {
for (int k = 0; k < 4; ++k) {
uint8_t byteA = (uint8_t)w;
uint8_t byteB = (uint8_t)(w >> 8);
w >>= 16;
__m128i vecA = _mm_loadu_si128(
(const __m128i *)vecDecodeTable_uint16[byteA]);
__m128i vecB = _mm_loadu_si128(
(const __m128i *)vecDecodeTable_uint16[byteB]);
uint8_t advanceA = lengthTable[byteA];
uint8_t advanceB = lengthTable[byteB];
vecA = _mm_add_epi16(baseVec, vecA);
baseVec = _mm_add_epi16(baseVec, add8);
vecB = _mm_add_epi16(baseVec, vecB);
baseVec = _mm_add_epi16(baseVec, add8);
_mm_storeu_si128((__m128i *)out, vecA);
out += advanceA;
_mm_storeu_si128((__m128i *)out, vecB);
out += advanceB;
}
}
}
base += (uint16_t)(i * 64);
for (; (i < length) && (out < safeout); ++i) {
uint64_t w = words[i];
while ((w != 0) && (out < safeout)) {
int r = roaring_trailing_zeroes(w);
*out = (uint16_t)(r + base);
out++;
w &= (w - 1);
}
base += 64;
}
return out - initout;
}
CROARING_UNTARGET_AVX2
#endif
/*
* Given a bitset containing "length" 64-bit words, write out the position
* of all the set bits to "out", values start at "base" (can be set to zero).
*
* The "out" pointer should be sufficient to store the actual number of bits
*set.
*
* Returns how many values were actually decoded.
*/
size_t bitset_extract_setbits_uint16(const uint64_t *words, size_t length,
uint16_t *out, uint16_t base) {
int outpos = 0;
for (size_t i = 0; i < length; ++i) {
uint64_t w = words[i];
while (w != 0) {
int r = roaring_trailing_zeroes(w);
out[outpos++] = (uint16_t)(r + base);
w &= (w - 1);
}
base += 64;
}
return outpos;
}
#if defined(CROARING_ASMBITMANIPOPTIMIZATION) && defined(CROARING_IS_X64)
static inline uint64_t _asm_bitset_set_list_withcard(uint64_t *words,
uint64_t card,
const uint16_t *list,
uint64_t length) {
uint64_t offset, load, pos;
uint64_t shift = 6;
const uint16_t *end = list + length;
if (!length) return card;
// TODO: could unroll for performance, see bitset_set_list
// bts is not available as an intrinsic in GCC
__asm volatile(
"1:\n"
"movzwq (%[list]), %[pos]\n"
"shrx %[shift], %[pos], %[offset]\n"
"mov (%[words],%[offset],8), %[load]\n"
"bts %[pos], %[load]\n"
"mov %[load], (%[words],%[offset],8)\n"
"sbb $-1, %[card]\n"
"add $2, %[list]\n"
"cmp %[list], %[end]\n"
"jnz 1b"
: [card] "+&r"(card), [list] "+&r"(list), [load] "=&r"(load),
[pos] "=&r"(pos), [offset] "=&r"(offset)
: [end] "r"(end), [words] "r"(words), [shift] "r"(shift));
return card;
}
static inline void _asm_bitset_set_list(uint64_t *words, const uint16_t *list,
uint64_t length) {
uint64_t pos;
const uint16_t *end = list + length;
uint64_t shift = 6;
uint64_t offset;
uint64_t load;
for (; list + 3 < end; list += 4) {
pos = list[0];
__asm volatile(
"shrx %[shift], %[pos], %[offset]\n"
"mov (%[words],%[offset],8), %[load]\n"
"bts %[pos], %[load]\n"
"mov %[load], (%[words],%[offset],8)"
: [load] "=&r"(load), [offset] "=&r"(offset)
: [words] "r"(words), [shift] "r"(shift), [pos] "r"(pos));
pos = list[1];
__asm volatile(
"shrx %[shift], %[pos], %[offset]\n"
"mov (%[words],%[offset],8), %[load]\n"
"bts %[pos], %[load]\n"
"mov %[load], (%[words],%[offset],8)"
: [load] "=&r"(load), [offset] "=&r"(offset)
: [words] "r"(words), [shift] "r"(shift), [pos] "r"(pos));
pos = list[2];
__asm volatile(
"shrx %[shift], %[pos], %[offset]\n"
"mov (%[words],%[offset],8), %[load]\n"
"bts %[pos], %[load]\n"
"mov %[load], (%[words],%[offset],8)"
: [load] "=&r"(load), [offset] "=&r"(offset)
: [words] "r"(words), [shift] "r"(shift), [pos] "r"(pos));
pos = list[3];
__asm volatile(
"shrx %[shift], %[pos], %[offset]\n"
"mov (%[words],%[offset],8), %[load]\n"
"bts %[pos], %[load]\n"
"mov %[load], (%[words],%[offset],8)"
: [load] "=&r"(load), [offset] "=&r"(offset)
: [words] "r"(words), [shift] "r"(shift), [pos] "r"(pos));
}
while (list != end) {
pos = list[0];
__asm volatile(
"shrx %[shift], %[pos], %[offset]\n"
"mov (%[words],%[offset],8), %[load]\n"
"bts %[pos], %[load]\n"
"mov %[load], (%[words],%[offset],8)"
: [load] "=&r"(load), [offset] "=&r"(offset)
: [words] "r"(words), [shift] "r"(shift), [pos] "r"(pos));
list++;
}
}
static inline uint64_t _asm_bitset_clear_list(uint64_t *words, uint64_t card,
const uint16_t *list,
uint64_t length) {
uint64_t offset, load, pos;
uint64_t shift = 6;
const uint16_t *end = list + length;
if (!length) return card;
// btr is not available as an intrinsic in GCC
__asm volatile(
"1:\n"
"movzwq (%[list]), %[pos]\n"
"shrx %[shift], %[pos], %[offset]\n"
"mov (%[words],%[offset],8), %[load]\n"
"btr %[pos], %[load]\n"
"mov %[load], (%[words],%[offset],8)\n"
"sbb $0, %[card]\n"
"add $2, %[list]\n"
"cmp %[list], %[end]\n"
"jnz 1b"
: [card] "+&r"(card), [list] "+&r"(list), [load] "=&r"(load),
[pos] "=&r"(pos), [offset] "=&r"(offset)
: [end] "r"(end), [words] "r"(words), [shift] "r"(shift)
:
/* clobbers */ "memory");
return card;
}
static inline uint64_t _scalar_bitset_clear_list(uint64_t *words, uint64_t card,
const uint16_t *list,
uint64_t length) {
uint64_t offset, load, newload, pos, index;
const uint16_t *end = list + length;
while (list != end) {
pos = *(const uint16_t *)list;
offset = pos >> 6;
index = pos % 64;
load = words[offset];
newload = load & ~(UINT64_C(1) << index);
card -= (load ^ newload) >> index;
words[offset] = newload;
list++;
}
return card;
}
static inline uint64_t _scalar_bitset_set_list_withcard(uint64_t *words,
uint64_t card,
const uint16_t *list,
uint64_t length) {
uint64_t offset, load, newload, pos, index;
const uint16_t *end = list + length;
while (list != end) {
pos = *list;
offset = pos >> 6;
index = pos % 64;
load = words[offset];
newload = load | (UINT64_C(1) << index);
card += (load ^ newload) >> index;
words[offset] = newload;
list++;
}
return card;
}
static inline void _scalar_bitset_set_list(uint64_t *words,
const uint16_t *list,
uint64_t length) {
uint64_t offset, load, newload, pos, index;
const uint16_t *end = list + length;
while (list != end) {
pos = *list;
offset = pos >> 6;
index = pos % 64;
load = words[offset];
newload = load | (UINT64_C(1) << index);
words[offset] = newload;
list++;
}
}
uint64_t bitset_clear_list(uint64_t *words, uint64_t card, const uint16_t *list,
uint64_t length) {
if (croaring_hardware_support() & ROARING_SUPPORTS_AVX2) {
return _asm_bitset_clear_list(words, card, list, length);
} else {
return _scalar_bitset_clear_list(words, card, list, length);
}
}
uint64_t bitset_set_list_withcard(uint64_t *words, uint64_t card,
const uint16_t *list, uint64_t length) {
if (croaring_hardware_support() & ROARING_SUPPORTS_AVX2) {
return _asm_bitset_set_list_withcard(words, card, list, length);
} else {
return _scalar_bitset_set_list_withcard(words, card, list, length);
}
}
void bitset_set_list(uint64_t *words, const uint16_t *list, uint64_t length) {
if (croaring_hardware_support() & ROARING_SUPPORTS_AVX2) {
_asm_bitset_set_list(words, list, length);
} else {
_scalar_bitset_set_list(words, list, length);
}
}
#else
uint64_t bitset_clear_list(uint64_t *words, uint64_t card, const uint16_t *list,
uint64_t length) {
uint64_t offset, load, newload, pos, index;
const uint16_t *end = list + length;
while (list != end) {
pos = *(const uint16_t *)list;
offset = pos >> 6;
index = pos % 64;
load = words[offset];
newload = load & ~(UINT64_C(1) << index);
card -= (load ^ newload) >> index;
words[offset] = newload;
list++;
}
return card;
}
uint64_t bitset_set_list_withcard(uint64_t *words, uint64_t card,
const uint16_t *list, uint64_t length) {
uint64_t offset, load, newload, pos, index;
const uint16_t *end = list + length;
while (list != end) {
pos = *list;
offset = pos >> 6;
index = pos % 64;
load = words[offset];
newload = load | (UINT64_C(1) << index);
card += (load ^ newload) >> index;
words[offset] = newload;
list++;
}
return card;
}
void bitset_set_list(uint64_t *words, const uint16_t *list, uint64_t length) {
uint64_t offset, load, newload, pos, index;
const uint16_t *end = list + length;
while (list != end) {
pos = *list;
offset = pos >> 6;
index = pos % 64;
load = words[offset];
newload = load | (UINT64_C(1) << index);
words[offset] = newload;
list++;
}
}
#endif
/* flip specified bits */
/* TODO: consider whether worthwhile to make an asm version */
uint64_t bitset_flip_list_withcard(uint64_t *words, uint64_t card,
const uint16_t *list, uint64_t length) {
uint64_t offset, load, newload, pos, index;
const uint16_t *end = list + length;
while (list != end) {
pos = *list;
offset = pos >> 6;
index = pos % 64;
load = words[offset];
newload = load ^ (UINT64_C(1) << index);
// todo: is a branch here all that bad?
card +=
(1 - 2 * (((UINT64_C(1) << index) & load) >> index)); // +1 or -1
words[offset] = newload;
list++;
}
return card;
}
void bitset_flip_list(uint64_t *words, const uint16_t *list, uint64_t length) {
uint64_t offset, load, newload, pos, index;
const uint16_t *end = list + length;
while (list != end) {
pos = *list;
offset = pos >> 6;
index = pos % 64;
load = words[offset];
newload = load ^ (UINT64_C(1) << index);
words[offset] = newload;
list++;
}
}
#ifdef __cplusplus
}
}
} // extern "C" { namespace roaring { namespace api {
#endif
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC diagnostic pop
#endif