#include <string.h>

typedef unsigned vu __attribute__ ((vector_size (UNROLL*sizeof(unsigned))));

unsigned keylocks(unsigned keys[], unsigned nkeys, unsigned locks[], unsigned nlocks)
{
  unsigned i, j;
  unsigned part1 = 0;
  /* that's apparently 0:
     https://stackoverflow.com/questions/40730815/gnu-c-native-vectors-how-to-broadcast-a-scalar-like-x86s-mm-set1-epi16 */
  vu acc0=(vu){};
  vu acc1=(vu){};
  vu acc2=(vu){};
  vu acc3=(vu){};
  int nlocks1=(nlocks+UNROLL*8-1)&(-(UNROLL*8));
  int nkeys1;
  int locks1[nlocks1];
  int keys1[nkeys];
  for (i=0; i<nlocks; i++)
    locks1[i]=locks[i];
  for (; i<nlocks1; i++)
    locks1[i]=~0;
  /* special-casing for 0 keys, to avoid counting the extra locks */
  for (i=0, nkeys1=0; i<nkeys; i++)
    if (keys[i] != 0)
      keys1[nkeys1++]=keys[i];
    else
      part1+=nlocks;
  for (i=0; i<nlocks1; i+=UNROLL*8) {
    vu lock0 = *(vu *)(locks1+i+0*UNROLL);
    vu lock1 = *(vu *)(locks1+i+1*UNROLL);
    vu lock2 = *(vu *)(locks1+i+2*UNROLL);
    vu lock3 = *(vu *)(locks1+i+3*UNROLL);
    vu lock4 = *(vu *)(locks1+i+4*UNROLL);
    vu lock5 = *(vu *)(locks1+i+5*UNROLL);
    vu lock6 = *(vu *)(locks1+i+6*UNROLL);
    vu lock7 = *(vu *)(locks1+i+7*UNROLL);
    for (j=0; j<nkeys1; j++) {
      vu key = keys1[j] - (vu){}; /* the "(vu){} is there to convert to vu */
      acc0 -= (lock0 & key)==0;
      acc1 -= (lock1 & key)==0;
      acc2 -= (lock2 & key)==0;
      acc3 -= (lock3 & key)==0;
      acc0 -= (lock4 & key)==0;
      acc1 -= (lock5 & key)==0;
      acc2 -= (lock6 & key)==0;
      acc3 -= (lock7 & key)==0;
    }
  }
  acc0 += acc1;
  acc2 += acc3;
  acc0 += acc2;
  for (i=0; i<UNROLL; i++)
    part1 += acc0[i];
  return part1;
}