/***************************************************************************

 *                                  _   _ ____  _

 *  Project                     ___| | | |  _ \| |

 *                             / __| | | | |_) | |

 *                            | (__| |_| |  _ <| |___

 *                             \___|\___/|_| \_\_____|

 *

 * Copyright (C) Daniel Stenberg, <daniel@haxx.se>, et al.

 *

 * This software is licensed as described in the file COPYING, which

 * you should have received as part of this distribution. The terms

 * are also available at https://curl.se/docs/copyright.html.

 *

 * You may opt to use, copy, modify, merge, publish, distribute and/or sell

 * copies of the Software, and permit persons to whom the Software is

 * furnished to do so, under the terms of the COPYING file.

 *

 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY

 * KIND, either express or implied.

 *

 * SPDX-License-Identifier: curl

 *

 ***************************************************************************/

#include "curl_setup.h"

#include "uint-bset.h"

#ifdef DEBUGBUILD

#define CURL_UINT32_BSET_MAGIC  0x62757473

#endif

void Curl_uint32_bset_init(struct uint32_bset *bset)

{

  memset(bset, 0, sizeof(*bset));

#ifdef DEBUGBUILD

  bset->init = CURL_UINT32_BSET_MAGIC;

#endif

}

CURLcode Curl_uint32_bset_resize(struct uint32_bset *bset, uint32_t nmax)

{

  uint32_t nslots = (nmax < (UINT32_MAX - 63)) ?

                    ((nmax + 63) / 64) : (UINT32_MAX / 64);

  DEBUGASSERT(bset->init == CURL_UINT32_BSET_MAGIC);

  if(nslots != bset->nslots) {

    uint64_t *slots = curlx_calloc(nslots, sizeof(uint64_t));

    if(!slots)

      return CURLE_OUT_OF_MEMORY;

    if(bset->slots) {

      memcpy(slots, bset->slots,

             (CURLMIN(nslots, bset->nslots) * sizeof(uint64_t)));

      curlx_free(bset->slots);

    }

    bset->slots = slots;

    bset->nslots = nslots;

    bset->first_slot_used = 0;

  }

  return CURLE_OK;

}

void Curl_uint32_bset_destroy(struct uint32_bset *bset)

{

  DEBUGASSERT(bset->init == CURL_UINT32_BSET_MAGIC);

  curlx_free(bset->slots);

  memset(bset, 0, sizeof(*bset));

}

#ifdef UNITTESTS

UNITTEST uint32_t Curl_uint32_bset_capacity(struct uint32_bset *bset);

UNITTEST uint32_t Curl_uint32_bset_capacity(struct uint32_bset *bset)

{

  return bset->nslots * 64;

}

#endif

uint32_t Curl_uint32_bset_count(struct uint32_bset *bset)

{

  uint32_t i;

  uint32_t n = 0;

  for(i = 0; i < bset->nslots; ++i) {

    if(bset->slots[i])

      n += CURL_POPCOUNT64(bset->slots[i]);

  }

  return n;

}

bool Curl_uint32_bset_empty(struct uint32_bset *bset)

{

  uint32_t i;

  for(i = bset->first_slot_used; i < bset->nslots; ++i) {

    if(bset->slots[i])

      return FALSE;

  }

  return TRUE;

}

void Curl_uint32_bset_clear(struct uint32_bset *bset)

{

  if(bset->nslots) {

    memset(bset->slots, 0, bset->nslots * sizeof(uint64_t));

    bset->first_slot_used = UINT32_MAX;

  }

}

bool Curl_uint32_bset_add(struct uint32_bset *bset, uint32_t i)

{

  uint32_t islot = i / 64;

  if(islot >= bset->nslots)

    return FALSE;

  bset->slots[islot] |= ((uint64_t)1 << (i % 64));

  if(islot < bset->first_slot_used)

    bset->first_slot_used = islot;

  return TRUE;

}

void Curl_uint32_bset_remove(struct uint32_bset *bset, uint32_t i)

{

  size_t islot = i / 64;

  if(islot < bset->nslots)

    bset->slots[islot] &= ~((uint64_t)1 << (i % 64));

}

bool Curl_uint32_bset_contains(struct uint32_bset *bset, uint32_t i)

{

  uint32_t islot = i / 64;

  if(islot >= bset->nslots)

    return FALSE;

  return (bset->slots[islot] & ((uint64_t)1 << (i % 64))) != 0;

}

bool Curl_uint32_bset_first(struct uint32_bset *bset, uint32_t *pfirst)

{

  uint32_t i;

  for(i = bset->first_slot_used; i < bset->nslots; ++i) {

    if(bset->slots[i]) {

      *pfirst = (i * 64) + CURL_CTZ64(bset->slots[i]);

      bset->first_slot_used = i;

      return TRUE;

    }

  }

  bset->first_slot_used = *pfirst = UINT32_MAX;

  return FALSE;

}

bool Curl_uint32_bset_next(struct uint32_bset *bset, uint32_t last,

                           uint32_t *pnext)

{

  uint32_t islot;

  uint64_t x;

  ++last; /* look for number one higher than last */

  islot = last / 64; /* the slot this would be in */

  if(islot < bset->nslots) {

    /* shift away the bits we already iterated in this slot */

    x = (bset->slots[islot] >> (last % 64));

    if(x) {

      /* more bits set, next is `last` + trailing0s of the shifted slot */

      *pnext = last + CURL_CTZ64(x);

      return TRUE;

    }

    /* no more bits set in the last slot, scan forward */

    for(islot = islot + 1; islot < bset->nslots; ++islot) {

      if(bset->slots[islot]) {

        *pnext = (islot * 64) + CURL_CTZ64(bset->slots[islot]);

        return TRUE;

      }

    }

  }

  *pnext = UINT32_MAX; /* a value we cannot store */

  return FALSE;

}

#ifdef CURL_POPCOUNT64_IMPLEMENT

uint32_t Curl_popcount64(uint64_t x)

{

  /* Compute the "Hamming Distance" between 'x' and 0,

   * which is the number of set bits in 'x'.

   * See: https://en.wikipedia.org/wiki/Hamming_weight */

  const uint64_t m1  = 0x5555555555555555LL; /* 0101+ */

  const uint64_t m2  = 0x3333333333333333LL; /* 00110011+ */

  const uint64_t m4  = 0x0f0f0f0f0f0f0f0fLL; /* 00001111+ */

   /* 1 + 256^1 + 256^2 + 256^3 + ... + 256^7 */

  const uint64_t h01 = 0x0101010101010101LL;

  x -= (x >> 1) & m1;             /* replace every 2 bits with bits present */

  x = (x & m2) + ((x >> 2) & m2); /* replace every nibble with bits present */

  x = (x + (x >> 4)) & m4;        /* replace every byte with bits present */

  /* top 8 bits of x + (x << 8) + (x << 16) + (x << 24) + ... which makes the

   * top byte the sum of all individual 8 bytes, throw away the rest */

  return (uint32_t)((x * h01) >> 56);

}

#endif /* CURL_POPCOUNT64_IMPLEMENT */

#ifdef CURL_CTZ64_IMPLEMENT

uint32_t Curl_ctz64(uint64_t x)

{

  /* count trailing zeros in a uint64_t.

   * divide and conquer to find the number of lower 0 bits */

  const uint64_t ml32 = 0xFFFFFFFF; /* lower 32 bits */

  const uint64_t ml16 = 0x0000FFFF; /* lower 16 bits */

  const uint64_t ml8  = 0x000000FF; /* lower 8 bits */

  const uint64_t ml4  = 0x0000000F; /* lower 4 bits */

  const uint64_t ml2  = 0x00000003; /* lower 2 bits */

  uint32_t n;

  if(!x)

    return 64;

  n = 1;

  if(!(x & ml32)) {

    n = n + 32;

    x = x >> 32;

  }

  if(!(x & ml16)) {

    n = n + 16;

    x = x >> 16;

  }

  if(!(x & ml8)) {

    n = n + 8;

    x = x >> 8;

  }

  if(!(x & ml4)) {

    n = n + 4;

    x = x >> 4;

  }

  if(!(x & ml2)) {

    n = n + 2;

    x = x >> 2;

  }

  return n - (uint32_t)(x & 1);

}

#endif /* CURL_CTZ64_IMPLEMENT */