#include "ccv.h"

#include "ccv_internal.h"

ccv_dense_matrix_t* ccv_get_dense_matrix(ccv_matrix_t* mat)

{

  int type = *(int*)mat;

  if (type & CCV_MATRIX_DENSE)

    return (ccv_dense_matrix_t*)mat;

  return 0;

}

ccv_sparse_matrix_t* ccv_get_sparse_matrix(ccv_matrix_t* mat)

{

  int type = *(int*)mat;

  if (type & CCV_MATRIX_SPARSE)

    return (ccv_sparse_matrix_t*)mat;

  return 0;

}

void ccv_visualize(ccv_matrix_t* a, ccv_matrix_t** b, int type)

{

  ccv_dense_matrix_t* da = ccv_get_dense_matrix(a);

  ccv_declare_derived_signature(sig, da->sig != 0, ccv_sign_with_literal("ccv_visualize"), da->sig, CCV_EOF_SIGN);

  ccv_dense_matrix_t* db = *b = ccv_dense_matrix_renew(*b, da->rows, da->cols, CCV_8U | CCV_C1, CCV_8U | CCV_C1, sig);

  ccv_object_return_if_cached(, db);

  ccv_dense_matrix_t* dc = 0;

  if (CCV_GET_CHANNEL(da->type) > CCV_C1)

  {

    ccv_flatten(da, (ccv_matrix_t**)&dc, 0, 0);

    da = dc;

  }

  int i, j;

  double minval = DBL_MAX, maxval = -DBL_MAX;

  unsigned char* aptr = da->data.u8;

  unsigned char* bptr = db->data.u8;

#define for_block(_, _for_get) \

  for (i = 0; i < da->rows; i++) \

  { \

    for (j = 0; j < da->cols; j++) \

    { \

      minval = ccv_min(minval, _for_get(aptr, j)); \

      maxval = ccv_max(maxval, _for_get(aptr, j)); \

    } \

    aptr += da->step; \

  } \

  aptr = da->data.u8; \

  for (i = 0; i < da->rows; i++) \

  { \

    for (j = 0; j < da->cols; j++) \

      bptr[j] = ccv_clamp((_for_get(aptr, j) - minval) * 255.0 / (maxval - minval), 0, 255); \

    aptr += da->step; \

    bptr += db->step; \

  }

  ccv_matrix_getter(da->type, for_block);

#undef for_block

  if (dc != 0)

    ccv_matrix_free(dc);

}

void ccv_zero(ccv_matrix_t* mat)

{

  ccv_dense_matrix_t* dmt = ccv_get_dense_matrix(mat);

  memset(dmt->data.u8, 0, dmt->step * dmt->rows);

}

int ccv_any_nan(ccv_matrix_t *a)

{

  ccv_dense_matrix_t* da = ccv_get_dense_matrix(a);

  assert((da->type & CCV_32F) || (da->type & CCV_64F));

  int ch = CCV_GET_CHANNEL(da->type);

  int i;

  if (da->type & CCV_32F)

  {

    for (i = 0; i < da->rows * da->cols * ch; 
i++460M
)

#ifdef isnanf

      if (isnanf(da->data.f32[i]))

#else

      if (isnan(da->data.f32[i]))

#endif

        return i + 1;

  } else {

    for (i = 0; i < da->rows * da->cols * ch; i++)

      if (isnan(da->data.f64[i]))

        return i + 1;

  }

  return 0;

}

void ccv_flatten(ccv_matrix_t* a, ccv_matrix_t** b, int type, int flag)

{

  ccv_dense_matrix_t* da = ccv_get_dense_matrix(a);

  ccv_declare_derived_signature(sig, da->sig != 0, ccv_sign_with_format(64, "ccv_flatten(%d)", flag), da->sig, CCV_EOF_SIGN);

  int no_8u_type = (da->type & CCV_8U) ? CCV_32S : 
da->type0
;

  type = (type == 0) ? CCV_GET_DATA_TYPE(no_8u_type) | CCV_C1 : 
CCV_GET_DATA_TYPE0
(type) | CCV_C10
;

  ccv_dense_matrix_t* db = *b = ccv_dense_matrix_renew(*b, da->rows, da->cols, CCV_ALL_DATA_TYPE | CCV_C1, type, sig);

  ccv_object_return_if_cached(, db);

  int i, j, k, ch = CCV_GET_CHANNEL(da->type);

  unsigned char* aptr = da->data.u8;

  unsigned char* bptr = db->data.u8;

#define for_block(_for_get, _for_type, _for_set) \

  
for (i = 0; 1
i < da->rows; 
i++2
) \

  { \

    for (j = 0; j < da->cols; 
j++4
) \

    { \

      _for_type sum = 0; \

      for (k = 0; k < ch; 
k++8
) \

        sum += 
_for_get4
(aptr, j * ch + k); \

      _for_set(bptr, j, sum); \

    } \

    aptr += da->step; \

    bptr += db->step; \

  }

  ccv_matrix_getter(da->type, ccv_matrix_typeof_setter, db->type, for_block);

#undef for_block

}

void ccv_border(ccv_matrix_t* a, ccv_matrix_t** b, int type, ccv_margin_t margin)

{

  ccv_dense_matrix_t* da = ccv_get_dense_matrix(a);

  ccv_declare_derived_signature(sig, da->sig != 0, ccv_sign_with_format(64, "ccv_border(%d,%d,%d,%d)", margin.left, margin.top, margin.right, margin.bottom), da->sig, CCV_EOF_SIGN);

  int ch = CCV_GET_CHANNEL(da->type);

  type = (type == 0) ? CCV_GET_DATA_TYPE(da->type) | ch : 
CCV_GET_DATA_TYPE0
(type) | ch0
;

  ccv_dense_matrix_t* db = *b = ccv_dense_matrix_renew(*b, da->rows + margin.top + margin.bottom, da->cols + margin.left + margin.right, CCV_ALL_DATA_TYPE | ch, type, sig);

  ccv_object_return_if_cached(, db);

  ccv_zero(db);

  int i, j;

  unsigned char* aptr = da->data.u8;

  unsigned char* bptr = db->data.u8 + margin.top * db->step + margin.left * ch * CCV_GET_DATA_TYPE_SIZE(db->type);

  if (CCV_GET_DATA_TYPE(da->type) == CCV_GET_DATA_TYPE(db->type))

  {

    // use memcpy to speedup

    size_t scan = da->cols * ch * CCV_GET_DATA_TYPE_SIZE(da->type);

    for (i = 0; i < da->rows; 
i++1
)

    {

      memcpy(bptr, aptr, scan);

      aptr += da->step;

      bptr += db->step;

    }

  } else {

#define for_block(_for_get, _for_type, _for_set) \

    for (i = 0; i < da->rows; i++) \

    { \

      for (j = 0; j < da->cols * ch; j++) \

      { \

        _for_set(bptr, j, _for_get(aptr, j)); \

      } \

      aptr += da->step; \

      bptr += db->step; \

    }

    ccv_matrix_getter(da->type, ccv_matrix_typeof_setter, db->type, for_block);

#undef for_block

  }

}

void ccv_shift(ccv_matrix_t* a, ccv_matrix_t** b, int type, int lr, int rr)

{

  ccv_dense_matrix_t* da = ccv_get_dense_matrix(a);

  ccv_declare_derived_signature(sig, da->sig != 0, ccv_sign_with_format(64, "ccv_shift(%d,%d)", lr, rr), da->sig, CCV_EOF_SIGN);

  type = (type == 0) ? 
CCV_GET_DATA_TYPE0
(da->type) | 0
CCV_GET_CHANNEL0
(da->type) : CCV_GET_DATA_TYPE(type) | CCV_GET_CHANNEL(da->type);

  ccv_dense_matrix_t* db = *b = ccv_dense_matrix_renew(*b, da->rows, da->cols, CCV_ALL_DATA_TYPE | CCV_GET_CHANNEL(da->type), type, sig); 

  ccv_object_return_if_cached(, db);

  int i, j, ch = CCV_GET_CHANNEL(da->type);

  unsigned char* aptr = da->data.u8;

  unsigned char* bptr = db->data.u8;

#define for_block(_for_get, _for_set) \

  
for (i = 0; 10
i < da->rows; 
i++5.20k
) \

  { \

    for (j = 0; j < da->cols * ch; 
j++8.88M
) \

    { \

      _for_set(bptr, j, _for_get(aptr, j, lr), rr); \

    } \

    aptr += da->step; \

    bptr += db->step; \

  }

  ccv_matrix_getter(da->type, ccv_matrix_setter, db->type, for_block);

#undef for_block

}

// From https://github.com/skarupke/flat_hash_map with anything overflows 32bit removed.

static uint32_t _ccv_sparse_matrix_index_for_hash(const uint32_t hash, const int prime_index)

{

  switch(prime_index)

  {

  case 0:

    return 0u;

  case 1:

    return hash % 2u;

  case 2:

    return hash % 3u;

  case 3:

    return hash % 5u;

  case 4:

    return hash % 7u;

  case 5:

    return hash % 11u;

  case 6:

    return hash % 13u;

  case 7:

    return hash % 17u;

  case 8:

    return hash % 23u;

  case 9:

    return hash % 29u;

  case 10:

    return hash % 37u;

  case 11:

    return hash % 47u;

  case 12:

    return hash % 59u;

  case 13:

    return hash % 73u;

  case 14:

    return hash % 97u;

  case 15:

    return hash % 127u;

  case 16:

    return hash % 151u;

  case 17:

    return hash % 197u;

  case 18:

    return hash % 251u;

  case 19:

    return hash % 313u;

  case 20:

    return hash % 397u;

  case 21:

    return hash % 499u;

  case 22:

    return hash % 631u;

  case 23:

    return hash % 797u;

  case 24:

    return hash % 1009u;

  case 25:

    return hash % 1259u;

  case 26:

    return hash % 1597u;

  case 27:

    return hash % 2011u;

  case 28:

    return hash % 2539u;

  case 29:

    return hash % 3203u;

  case 30:

    return hash % 4027u;

  case 31:

    return hash % 5087u;

  case 32:

    return hash % 6421u;

  case 33:

    return hash % 8089u;

  case 34:

    return hash % 10193u;

  case 35:

    return hash % 12853u;

  case 36:

    return hash % 16193u;

  case 37:

    return hash % 20399u;

  case 38:

    return hash % 25717u;

  case 39:

    return hash % 32401u;

  case 40:

    return hash % 40823u;

  case 41:

    return hash % 51437u;

  case 42:

    return hash % 64811u;

  case 43:

    return hash % 81649u;

  case 44:

    return hash % 102877u;

  case 45:

    return hash % 129607u;

  case 46:

    return hash % 163307u;

  case 47:

    return hash % 205759u;

  case 48:

    return hash % 259229u;

  case 49:

    return hash % 326617u;

  case 50:

    return hash % 411527u;

  case 51:

    return hash % 518509u;

  case 52:

    return hash % 653267u;

  case 53:

    return hash % 823117u;

  case 54:

    return hash % 1037059u;

  case 55:

    return hash % 1306601u;

  case 56:

    return hash % 1646237u;

  case 57:

    return hash % 2074129u;

  case 58:

    return hash % 2613229u;

  case 59:

    return hash % 3292489u;

  case 60:

    return hash % 4148279u;

  case 61:

    return hash % 5226491u;

  case 62:

    return hash % 6584983u;

  case 63:

    return hash % 8296553u;

  case 64:

    return hash % 10453007u;

  case 65:

    return hash % 13169977u;

  case 66:

    return hash % 16593127u;

  case 67:

    return hash % 20906033u;

  case 68:

    return hash % 26339969u;

  case 69:

    return hash % 33186281u;

  case 70:

    return hash % 41812097u;

  case 71:

    return hash % 52679969u;

  case 72:

    return hash % 66372617u;

  case 73:

    return hash % 83624237u;

  case 74:

    return hash % 105359939u;

  case 75:

    return hash % 132745199u;

  case 76:

    return hash % 167248483u;

  case 77:

    return hash % 210719881u;

  case 78:

    return hash % 265490441u;

  case 79:

    return hash % 334496971u;

  case 80:

    return hash % 421439783u;

  case 81:

    return hash % 530980861u;

  case 82:

    return hash % 668993977u;

  case 83:

    return hash % 842879579u;

  case 84:

    return hash % 1061961721u;

  case 85:

    return hash % 1337987929u;

  case 86:

    return hash % 1685759167u;

  case 87:

    return hash % 2123923447u;

  case 88:

    return hash % 2675975881u;

  case 89:

    return hash % 3371518343u;

  case 90:

    return hash % 4247846927u;

  case 91:

    return hash % 4294967291u;

  default:

    return hash;

  }

}

// prime numbers generated by the following method:

// 1. start with a prime p = 2

// 2. go to wolfram alpha and get p = NextPrime(2 * p)

// 3. repeat 2. until you overflow 32 bits

// you now have large gaps which you would hit if somebody called reserve() with an unlucky number.

// 4. to fill the gaps for every prime p go to wolfram alpha and get ClosestPrime(p * 2^(1/3)) and ClosestPrime(p * 2^(2/3)) and put those in the gaps

// 5. get PrevPrime(2^32) and put it at the end

const static uint32_t _ccv_sparse_prime[] =

{

  2u, 3u, 5u, 7u, 11u, 13u, 17u, 23u, 29u, 37u, 47u,

  59u, 73u, 97u, 127u, 151u, 197u, 251u, 313u, 397u,

  499u, 631u, 797u, 1009u, 1259u, 1597u, 2011u, 2539u,

  3203u, 4027u, 5087u, 6421u, 8089u, 10193u, 12853u, 16193u,

  20399u, 25717u, 32401u, 40823u, 51437u, 64811u, 81649u,

  102877u, 129607u, 163307u, 205759u, 259229u, 326617u,

  411527u, 518509u, 653267u, 823117u, 1037059u, 1306601u,

  1646237u, 2074129u, 2613229u, 3292489u, 4148279u, 5226491u,

  6584983u, 8296553u, 10453007u, 13169977u, 16593127u, 20906033u,

  26339969u, 33186281u, 41812097u, 52679969u, 66372617u,

  83624237u, 105359939u, 132745199u, 167248483u, 210719881u,

  265490441u, 334496971u, 421439783u, 530980861u, 668993977u,

  842879579u, 1061961721u, 1337987929u, 1685759167u, 2123923447u,

  2675975881u, 3371518343u, 4247846927u, 4294967291u

};

static uint8_t _ccv_sparse_matrix_index_next_size_over(const uint32_t size)

{

  int i;

  assert(sizeof(_ccv_sparse_prime) / sizeof(uint32_t) == 91);

  
for (i = 0; 126k
i < sizeof(_ccv_sparse_prime) / sizeof(uint32_t); 
i++567k
)

    if (_ccv_sparse_prime[i] > size)

      return i + 1;

  return sizeof(_ccv_sparse_prime) / sizeof(uint32_t) + 1;

}

static uint32_t _ccv_sparse_matrix_size_for_index(const int prime_index)

{

  return _ccv_sparse_prime[prime_index - 1];

}

static void _ccv_init_sparse_matrix_vector(ccv_sparse_matrix_vector_t* vector, const ccv_sparse_matrix_t* const mat)

{

  if (mat->type & CCV_DENSE_VECTOR)

  {

    const int vlen = (mat->major == CCV_SPARSE_COL_MAJOR) ? 
mat->rows0
 : mat->cols;

    const size_t cell_size = CCV_GET_DATA_TYPE_SIZE(mat->type) * CCV_GET_CHANNEL(mat->type);

    vector->size = vlen;

    vector->data.u8 = (uint8_t*)cccalloc(1, (cell_size * vlen + 15) & -16);

    return;

  }

  vector->prime_index = 1; // See ccv_util.c to know why this is 1 and why size is 2.

  vector->size = 2;

  vector->rnum = 0;

  const size_t cell_size_aligned = (CCV_GET_DATA_TYPE_SIZE(mat->type) * CCV_GET_CHANNEL(mat->type) + 3) & -4;

  vector->index = (ccv_sparse_matrix_index_t*)cccalloc(sizeof(ccv_sparse_matrix_index_t) + cell_size_aligned, vector->size);

}

static inline void _ccv_move_sparse_matrix_vector(ccv_sparse_matrix_index_t* const index, ccv_sparse_matrix_vector_t* const vector, const ccv_sparse_matrix_t* const mat, uint32_t k, uint32_t idx, int i, const uint32_t size, const int prime_index)

{

  uint32_t old_i = index[idx].i;

  index[idx].i = i;

  i = old_i;

  ccv_sparse_matrix_vector_t val = vector[idx];

  _ccv_init_sparse_matrix_vector(vector + idx, mat);

  // Move to next idx, this is already occupied.

  ++k;

  ++idx;

  for (; k < 255; 
++idx, ++k45.8k
)

  {

    if (idx >= size)

      idx = 0;

    if (!index[idx].ifbit)

    {

      index[idx].ifbit = k;

      index[idx].i = i;

      vector[idx] = val;

      return;

    }

    uint32_t j = index[idx].ifbit;

    if (k > j)

    {

      index[idx].ifbit = k;

      k = j;

      uint32_t old_i = index[idx].i;

      index[idx].i = i;

      i = old_i;

      ccv_sparse_matrix_vector_t old_val = vector[idx];

      vector[idx] = val;

      val = old_val;

    }

  }

  for (;; ++idx, ++k)

  {

    if (idx >= size)

      idx = 0;

    if (!index[idx].ifbit)

    {

      index[idx].ifbit = k > 0xff ? 0xff : k;

      index[idx].i = i;

      vector[idx] = val;

      return;

    }

    uint32_t j = index[idx].ifbit;

    if (j == 0xff)

      j = (size - _ccv_sparse_matrix_index_for_hash(index[idx].i + size - idx, prime_index)) + 2;

    if (k > j)

    {

      index[idx].ifbit = k > 0xff ? 0xff : k;

      k = j;

      uint32_t old_i = index[idx].i;

      index[idx].i = i;

      i = old_i;

      ccv_sparse_matrix_vector_t old_val = vector[idx];

      vector[idx] = val;

      val = old_val;

    }

  }

}

static ccv_sparse_matrix_vector_t* _ccv_get_or_add_sparse_matrix_vector(ccv_sparse_matrix_t* mat, int i)

{

  const uint32_t size = mat->size;

  ccv_sparse_matrix_index_t* const index = mat->index;

  ccv_sparse_matrix_vector_t* const vector = mat->vector;

  const int prime_index = mat->prime_index;

  uint32_t idx = _ccv_sparse_matrix_index_for_hash(i, prime_index);

  uint32_t k = 2;

  for (; k < 255; 
++idx, ++k714k
)

  {

    if (idx >= size)

      idx = 0;

    uint32_t j = index[idx].ifbit;

    if (k > j)

    {

      ++mat->rnum;

      index[idx].ifbit = k;

      if (!j)

      {

        index[idx].i = i;

        _ccv_init_sparse_matrix_vector(vector + idx, mat);

      } else

        _ccv_move_sparse_matrix_vector(index, vector, mat, j /* This is j not k because we are replacing it. */, idx, i, size, prime_index);

      return vector + idx;

    }

    if (index[idx].i == i)

      return vector + idx;

  }

  // Above or equal to 255, we need to fetch the key to recompute the distance every time now.

  for (;; ++idx, ++k)

  {

    if (idx >= size)

      idx = 0;

    uint32_t j = index[idx].ifbit;

    if (j == 0xff)

      j = (size - _ccv_sparse_matrix_index_for_hash(index[idx].i + size - idx, prime_index)) + 2;

    if (k > j)

    {

      ++mat->rnum;

      index[idx].ifbit = k > 0xff ? 0xff : k;

      if (!j)

      {

        index[idx].i = i;

        _ccv_init_sparse_matrix_vector(vector + idx, mat);

      } else

        _ccv_move_sparse_matrix_vector(index, vector, mat, j /* This is j not k because we are replacing it. */, idx, i, size, prime_index);

      return vector + idx;

    }

    if (index[idx].i == i)

      return vector + idx;

  }

  return 0;

}

ccv_sparse_matrix_vector_t* ccv_get_sparse_matrix_vector(const ccv_sparse_matrix_t* mat, int i)

{

  const uint32_t size = mat->size;

  ccv_sparse_matrix_index_t* index = mat->index;

  ccv_sparse_matrix_vector_t* vector = mat->vector;

  const int prime_index = mat->prime_index;

  uint32_t idx = _ccv_sparse_matrix_index_for_hash(i, prime_index);

  uint32_t k = 2;

  for (; k < 255; 
++idx, ++k3.68M
)

  {

    if (idx >= size)

      idx = 0;

    if (k > index[idx].ifbit)

      return 0;

    if (index[idx].i == i)

      return vector + idx;

  }

  // Above or equal to 255, we need to fetch the key to recompute the distance every time now.

  for (;; ++idx, ++k)

  {

    if (idx >= size)

      idx = 0;

    uint32_t j = index[idx].ifbit;

    if (j == 0xff)

      j = (size - _ccv_sparse_matrix_index_for_hash(index[idx].i + size - idx, prime_index)) + 2;

    if (k > j)

      return 0;

    if (index[idx].i == i)

      return vector + idx;

  }

  return 0;

}

ccv_numeric_data_t ccv_get_sparse_matrix_cell_from_vector(const ccv_sparse_matrix_t* mat, ccv_sparse_matrix_vector_t* vector, int vidx)

{

  ccv_numeric_data_t cell = {}; // zero-init.

  const size_t cell_size = CCV_GET_DATA_TYPE_SIZE(mat->type) * CCV_GET_CHANNEL(mat->type);

  if (mat->type & CCV_DENSE_VECTOR)

  {

    cell.u8 = vector->data.u8 + cell_size * vidx;

    return cell;

  }

  const size_t cell_size_aligned = (CCV_GET_DATA_TYPE_SIZE(mat->type) * CCV_GET_CHANNEL(mat->type) + 3) & -4;

  const size_t index_size = sizeof(ccv_sparse_matrix_index_t) + cell_size_aligned;

  const uint32_t size = vector->size;

  uint8_t* const index = (uint8_t*)vector->index;

  const int prime_index = vector->prime_index;

  uint32_t idx = _ccv_sparse_matrix_index_for_hash(vidx, prime_index);

  uint32_t k = 2;

  for (; k < 255; 
++idx, ++k976k
)

  {

    if (idx >= size)

      idx = 0;

    ccv_sparse_matrix_index_t* const index_idx = (ccv_sparse_matrix_index_t*)(index + index_size * idx);

    if (k > index_idx->ifbit)

      return cell;

    if (index_idx->i == vidx)

    {

      cell.u8 = (uint8_t*)(index_idx + 1);

      return cell;

    }

  }

  // Above or equal to 255, we need to fetch the key to recompute the distance every time now.

  for (;; ++idx, ++k)

  {

    if (idx >= size)

      idx = 0;

    ccv_sparse_matrix_index_t* const index_idx = (ccv_sparse_matrix_index_t*)(index + index_size * idx);

    uint32_t j = index_idx->ifbit;

    if (j == 0xff)

      j = (size - _ccv_sparse_matrix_index_for_hash(index_idx->i + size - idx, prime_index)) + 2;

    if (k > j)

      return cell;

    if (index_idx->i == vidx)

    {

      cell.u8 = (uint8_t*)(index_idx + 1);

      return cell;

    }

  }

}

ccv_numeric_data_t ccv_get_sparse_matrix_cell(const ccv_sparse_matrix_t* mat, int row, int col)

{

  ccv_sparse_matrix_vector_t* vector = ccv_get_sparse_matrix_vector(mat, (mat->major == CCV_SPARSE_COL_MAJOR) ? 
col0
 : row);

  if (!vector || 
!vector->rnum101M
)

    return (ccv_numeric_data_t){};

  const int vidx = (mat->major == CCV_SPARSE_COL_MAJOR) ? 
row0
 : col;

  return ccv_get_sparse_matrix_cell_from_vector(mat, vector, vidx);

}

static void _ccv_sparse_matrix_vector_inc_size(const ccv_sparse_matrix_t* const mat, ccv_sparse_matrix_vector_t* const vector)

{

  assert(vector->prime_index >= 0 && vector->prime_index < sizeof(_ccv_sparse_prime) / sizeof(int));

  const uint32_t size = vector->size;

  const int prime_index = vector->prime_index = _ccv_sparse_matrix_index_next_size_over(size * 2);

  const uint32_t new_size = vector->size = _ccv_sparse_matrix_size_for_index(vector->prime_index);

  assert(vector->prime_index >= 0 && vector->prime_index < sizeof(_ccv_sparse_prime) / sizeof(int));

  const size_t cell_size_aligned = (CCV_GET_DATA_TYPE_SIZE(mat->type) * CCV_GET_CHANNEL(mat->type) + 3) & -4;

  const size_t index_size = sizeof(ccv_sparse_matrix_index_t) + cell_size_aligned;

  const size_t cell_rnum = cell_size_aligned / sizeof(uint32_t);

  vector->index = (ccv_sparse_matrix_index_t*)ccrealloc(vector->index, index_size * new_size);

  uint8_t* const index = (uint8_t*)vector->index;

  memset(index + index_size * size, 0, index_size * (new_size - size));

  uint32_t i, h;

  for (i = 0; i < size; 
i++2.45M
)

  {

    ccv_sparse_matrix_index_t* index_i = (ccv_sparse_matrix_index_t*)(index + index_size * i);

    index_i->ifbit = !!index_i->ifbit; // Mark this as need to be moved around.

  }

  for (i = 0; i < size; 
i++2.45M
)

  {

    ccv_sparse_matrix_index_t* index_i = (ccv_sparse_matrix_index_t*)(index + index_size * i);

    if (index_i->ifbit == 1) // Encountered one need to be moved.

    {

      index_i->ifbit = 0;

      // This item is from old hash table, need to find a new location for it.

      uint32_t key = index_i->i;

      uint32_t* val = (uint32_t*)(index_i + 1);

      uint32_t k = 2;

      uint32_t idx = _ccv_sparse_matrix_index_for_hash(key, prime_index);

      for (; k < 255; 
++idx, ++k204k
)

      {

        if (idx >= new_size)

          idx = 0;

        ccv_sparse_matrix_index_t* index_idx = (ccv_sparse_matrix_index_t*)(index + index_size * idx);

        uint32_t j = index_idx->ifbit;

        if (!j)

        {

          index_idx->ifbit = k;

          index_idx->i = key;

          memcpy(index_idx + 1, val, cell_size_aligned);

          break;

        }

        if (k <= j) // j could be either a valid one or 1, in any case, this will pass.

          continue;

        index_idx->ifbit = k;

        uint32_t old_key = index_idx->i;

        index_idx->i = key;

        key = old_key;

        uint32_t* old_val = (uint32_t*)(index_idx + 1);

        for (h = 0; h < cell_rnum; 
h++68.7k
)

        {

          uint32_t v = old_val[h];

          old_val[h] = val[h];

          val[h] = v;

        }

        if (j != 1)

          k = j;

        else { // In this case, I cannot keep going with the idx, need to recompute idx as well restart k.

          idx = _ccv_sparse_matrix_index_for_hash(key, prime_index) - 1;

          k = 1; // Restart.

        }

      }

      if (k < 255)

        continue;

      for (;; ++idx, ++k)

      {

        if (idx >= new_size)

          idx = 0;

        ccv_sparse_matrix_index_t* index_idx = (ccv_sparse_matrix_index_t*)(index + index_size * idx);

        uint32_t j = index_idx->ifbit;

        if (!j)

        {

          index_idx->ifbit = k > 0xff ? 0xff : k;

          index_idx->i = key;

          memcpy(index_idx + 1, val, cell_size_aligned);

          break;

        }

        if (j == 0xff)

          j = (new_size - _ccv_sparse_matrix_index_for_hash((index_idx->i + new_size - idx), prime_index)) + 2; // This is valid because on overflow, unsigned is well defined.

        if (k <= j) // j could be either a valid one or 1, in any case, this will pass.

          continue;

        index_idx->ifbit = k > 0xff ? 0xff : k;

        uint32_t old_key = index_idx->i;

        index_idx->i = key;

        key = old_key;

        uint32_t* old_val = (uint32_t*)(index_idx + 1);

        for (h = 0; h < cell_rnum; h++)

        {

          uint32_t v = old_val[h];

          old_val[h] = val[h];

          val[h] = v;

        }

        if (j != 1)

          k = j;

        else { // In this case, I cannot keep going with the idx, need to recompute idx as well restart k.

          idx = _ccv_sparse_matrix_index_for_hash(key, prime_index) - 1;

          k = 1; // Restart.

        }

      }

    }

  }

}

static void _ccv_sparse_matrix_inc_size(ccv_sparse_matrix_t* mat)

{

  assert(mat->prime_index >= 0 && mat->prime_index < sizeof(_ccv_sparse_prime) / sizeof(int));

  const uint32_t size = mat->size;

  const int prime_index = mat->prime_index = _ccv_sparse_matrix_index_next_size_over(size * 2);

  const uint32_t new_size = mat->size = _ccv_sparse_matrix_size_for_index(mat->prime_index);

  assert(mat->prime_index >= 0 && mat->prime_index < sizeof(_ccv_sparse_prime) / sizeof(int));

  ccv_sparse_matrix_index_t* const index = mat->index = (ccv_sparse_matrix_index_t*)ccrealloc(mat->index, sizeof(ccv_sparse_matrix_index_t) * new_size);

  memset(index + size, 0, sizeof(ccv_sparse_matrix_index_t) * (new_size - size));

  ccv_sparse_matrix_vector_t* const vector = mat->vector = (ccv_sparse_matrix_vector_t*)ccrealloc(mat->vector, sizeof(ccv_sparse_matrix_vector_t) * new_size);

  uint32_t i;

  for (i = 0; i < size; 
i++104k
)

    index[i].ifbit = !!index[i].ifbit; // Mark this as need to be moved around.

  for (i = 0; i < size; 
i++104k
)

    if (index[i].ifbit == 1) // Encountered one need to be moved.

    {

      index[i].ifbit = 0;

      // This item is from old hash table, need to find a new location for it.

      uint32_t key = index[i].i;

      ccv_sparse_matrix_vector_t val = vector[i];

      uint32_t k = 2;

      uint32_t idx = _ccv_sparse_matrix_index_for_hash(key, prime_index);

      for (; k < 255; 
++idx, ++k19.3k
)

      {

        if (idx >= new_size)

          idx = 0;

        uint32_t j = index[idx].ifbit;

        if (!j)

        {

          index[idx].ifbit = k;

          index[idx].i = key;

          vector[idx] = val;

          break;

        }

        if (k <= j) // j could be either a valid one or 1, in any case, this will pass.

          continue;

        index[idx].ifbit = k;

        uint32_t old_key = index[idx].i;

        index[idx].i = key;

        key = old_key;

        ccv_sparse_matrix_vector_t old_val = vector[idx];

        vector[idx] = val;

        val = old_val;

        if (j != 1)

          k = j;

        else { // In this case, I cannot keep going with the idx, need to recompute idx as well restart k.

          idx = _ccv_sparse_matrix_index_for_hash(key, prime_index) - 1;

          k = 1; // Restart.

        }

      }

      if (k < 255)

        continue;

      for (;; ++idx, ++k)

      {

        if (idx >= new_size)

          idx = 0;

        uint32_t j = index[idx].ifbit;

        if (!j)

        {

          index[idx].ifbit = k > 0xff ? 0xff : k;

          index[idx].i = key;

          vector[idx] = val;

          break;

        }

        if (j == 0xff)

          j = (new_size - _ccv_sparse_matrix_index_for_hash((index[idx].i + new_size - idx), prime_index)) + 2; // This is valid because on overflow, unsigned is well defined.

        if (k <= j) // j could be either a valid one or 1, in any case, this will pass.

          continue;

        index[idx].ifbit = k > 0xff ? 0xff : k;

        uint32_t old_key = index[idx].i;

        index[idx].i = key;

        key = old_key;

        ccv_sparse_matrix_vector_t old_val = vector[idx];

        vector[idx] = val;

        val = old_val;

        if (j != 1)

          k = j;

        else { // In this case, I cannot keep going with the idx, need to recompute idx as well restart k.

          idx = _ccv_sparse_matrix_index_for_hash(key, prime_index) - 1;

          k = 1; // Restart.

        }

      }

    }

}

static inline void _ccv_move_sparse_matrix_cell(uint8_t* const index, uint32_t k, uint32_t idx, int i, const uint32_t size, const int prime_index, const size_t index_size, const size_t cell_size_aligned)

{

  ccv_sparse_matrix_index_t* const index_idx = (ccv_sparse_matrix_index_t*)(index + index_size * idx);

  const size_t cell_rnum = cell_size_aligned / sizeof(uint32_t);

  uint32_t* val = (uint32_t*)(index_idx + 1);

  uint32_t old_i = index_idx->i;

  index_idx->i = i;

  i = old_i;

  // Move to next idx, this is already occupied.

  ++k;

  ++idx;

  uint32_t h;

  for (; k < 255; 
++idx, ++k530k
)

  {

    if (idx >= size)

      idx = 0;

    ccv_sparse_matrix_index_t* const index_idx = (ccv_sparse_matrix_index_t*)(index + index_size * idx);

    if (!index_idx->ifbit)

    {

      index_idx->ifbit = k;

      index_idx->i = i;

      memcpy(index_idx + 1, val, cell_size_aligned);

      return;

    }

    uint32_t j = index_idx->ifbit;

    if (k > j)

    {

      index_idx->ifbit = k;

      k = j;

      uint32_t old_i = index_idx->i;

      index_idx->i = i;

      i = old_i;

      uint32_t* old_val = (uint32_t*)(index_idx + 1);

      for (h = 0; h < cell_rnum; 
h++494k
)

      {

        uint32_t v = old_val[h];

        old_val[h] = val[h];

        val[h] = v;

      }

    }

  }

  for (;; ++idx, ++k)

  {

    if (idx >= size)

      idx = 0;

    ccv_sparse_matrix_index_t* const index_idx = (ccv_sparse_matrix_index_t*)(index + index_size * idx);

    if (!index_idx->ifbit)

    {

      index_idx->ifbit = k > 0xff ? 0xff : k;

      index_idx->i = i;

      memcpy(index_idx + 1, val, cell_size_aligned);

      return;

    }

    uint32_t j = index_idx->ifbit;

    if (j == 0xff)

      j = (size - _ccv_sparse_matrix_index_for_hash(index_idx->i + size - idx, prime_index)) + 2;

    if (k > j)

    {

      index_idx->ifbit = k > 0xff ? 0xff : k;

      k = j;

      uint32_t old_i = index_idx->i;

      index_idx->i = i;

      i = old_i;

      uint32_t* old_val = (uint32_t*)(index_idx + 1);

      for (h = 0; h < cell_rnum; h++)

      {

        uint32_t v = old_val[h];

        old_val[h] = val[h];

        val[h] = v;

      }

    }

  }