Scikit-learn
human-activity-recognition
wearable
wrist
time-series
cpu
scikit-learn
WISP / src /wisp_fast /funnel /interval_levels.h
Zipeng365's picture
wisp-har 0.4.0: WISP-Funnel search and the adaptive HMM switch (default decoder)
93a9282 verified
Raw History Blame Contribute Delete
6.43 kB
/* Each bin may represent exactly one observed double. Detect collisions and
* let the original ranking routine take over. In each time-prefix vector,
* byte b counts samples with value <= bin b (T<=255). */
#if defined(CAN_FILTER)
typedef struct {unsigned char lo,hi;double frac;} LevelCut;
/* Assign each sample the count of strictly smaller samples. Equal values
therefore share a code; the gaps in rank space are harmless for a CDF. */
__attribute__((target("avx512bw,avx512f")))
static void rank_codes64(const double *src,int t,int c,unsigned char *key,double *values){
double v[64];for(int j=0;j<t;++j)v[j]=src[j*c];
for(int j=0;j<t;j+=8){
__mmask8 valid=t-j>=8?255:(1u<<(t-j))-1;
__m512d x=_mm512_maskz_loadu_pd(valid,v+j);__m512i ranks=_mm512_setzero_si512(),one=_mm512_set1_epi64(1);
for(int h=0;h<t;++h)ranks=_mm512_mask_add_epi64(ranks,_mm512_cmp_pd_mask(x,_mm512_set1_pd(v[h]),_CMP_GT_OQ),ranks,one);
_mm512_mask_cvtepi64_storeu_epi8(key+j,valid,ranks);
}
for(int j=0;j<t;++j)values[key[j]]=v[j];
}
__attribute__((target("avx512bw,avx512f")))
static int level_cdf(const double *src,int t,int c,const int64_t *bounds,int m,
const LevelCut *cuts,int nq,int width,int turbo,double *out,int ch){
double min=src[0],max=src[0],values[64];uint64_t used=0;
for(int j=0;j<t;++j){double v=src[j*c];if(!isfinite(v)||(v==0. && signbit(v)))return 0;
if(v<min)min=v;if(v>max)max=v;}
/* Accepted values also bound every numeric interval moment far below DBL_MAX. */
if(min < -1.e140 || max > 1.e140)return 0;
double span=max-min,scale=span?63./span:0.;
if(!isfinite(scale)||!isfinite(span))return 0;
unsigned char key[256];
for(int j=0;j<t;++j){double v=src[j*c];int k=(int)((v-min)*scale+.5);if(k>63)k=63;
uint64_t bit=UINT64_C(1)<<k;
if((used&bit) && values[k]!=v){
if(t>64)return 0;
rank_codes64(src,t,c,key,values);break;
}
values[k]=v;used|=bit;key[j]=(unsigned char)k;
}
static const unsigned char index[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};
__m512i prefix[256],cdf=_mm512_setzero_si512(),one=_mm512_set1_epi8(1),bins=_mm512_loadu_si512(index);
prefix[0]=cdf;
for(int j=0;j<t;++j){
__mmask64 update=_mm512_cmpge_epu8_mask(bins,_mm512_set1_epi8(key[j]));
cdf=_mm512_mask_add_epi8(cdf,update,cdf,one);prefix[j+1]=cdf;
}
for(int j=0;j<m;++j){
int a=bounds[2*j],b=bounds[2*j+1],n=b-a;
__m512i f=_mm512_sub_epi8(prefix[b],prefix[a]);
int low=__builtin_ctzll(_mm512_cmpneq_epi8_mask(f,_mm512_setzero_si512()));
int high=__builtin_ctzll(_mm512_cmpeq_epi8_mask(f,_mm512_set1_epi8((char)n)));
double *dst=out+j*width*c;dst[2*c+ch]=values[high]-values[low];
for(int h=0;h<nq;++h){const LevelCut *s=cuts+j*nq+h;
int lo=__builtin_ctzll(_mm512_cmpgt_epu8_mask(f,_mm512_set1_epi8((char)s->lo)));
int hi=__builtin_ctzll(_mm512_cmpgt_epu8_mask(f,_mm512_set1_epi8((char)s->hi)));
double x=values[lo],y=values[hi],q=s->frac;
dst[(width-nq)*c+ch*nq+h]=turbo?((n&1)?x:(x+y)*.5):(q>=.5?y-(y-x)*(1.-q):x+(y-x)*q);
}
}
return 1;
}
#endif
static PyObject *interval_levels(PyObject *self,PyObject *args){
PyObject *obj[4];int turbo,partial=0;Py_buffer v[4]={{0}};int ok=0;PyObject *mask=NULL;
if(!PyArg_ParseTuple(args,"OOOOi|p",&obj[0],&obj[1],&obj[2],&obj[3],&turbo,&partial))return NULL;
if(!view(obj[0],v,3,'d',0)||!view(obj[1],v+1,2,'q',0)||!view(obj[2],v+2,1,'d',0)||
!view(obj[3],v+3,3,'d',1)||!separate_output(v,3))goto done;
Py_ssize_t n=v[0].shape[0],t=v[0].shape[1],c=v[0].shape[2],m=v[1].shape[0],nq=v[2].shape[0];
int width=(turbo?3:5)+(int)nq;const double *q=v[2].buf;const int64_t *bounds=v[1].buf;
if(n<1||t<1||t>255||c<2||c>256||m<1||m>65536||nq<1||nq>16||v[1].shape[1]!=2||
v[3].shape[0]!=n||v[3].shape[1]!=m||v[3].shape[2]!=c*width||
(turbo && (nq!=1||q[0]!=.5))){
PyErr_SetString(PyExc_ValueError,"unsupported bounded CDF geometry");goto done;
}
for(int j=0;j<nq;++j)if(!isfinite(q[j])||q[j]<0||q[j]>1){PyErr_SetString(PyExc_ValueError,"invalid quantile");goto done;}
for(int j=0;j<m;++j)if(bounds[2*j]<0||bounds[2*j+1]>t||bounds[2*j]>=bounds[2*j+1]){
PyErr_SetString(PyExc_ValueError,"invalid interval");goto done;}
#ifdef CAN_FILTER
if(__builtin_cpu_supports("avx512bw") && CAN_FILTER){
LevelCut *cuts=PyMem_Malloc(m*nq*sizeof(*cuts));
double *tile=PyMem_Malloc(8*t*sizeof(double)),*out=v[3].buf;const double *x=v[0].buf;
if(!cuts || !tile){PyMem_Free(cuts);PyMem_Free(tile);PyErr_NoMemory();goto done;}
for(int j=0;j<m;++j)for(int h=0;h<nq;++h){int last=(int)(bounds[2*j+1]-bounds[2*j]-1);
double loc=last*q[h];int k=(int)loc;cuts[j*nq+h]=(LevelCut){k,k<last?k+1:k,loc-k};}
if(partial){
mask=PyBytes_FromStringAndSize(NULL,n);
if(!mask){PyMem_Free(cuts);PyMem_Free(tile);goto done;}
}
char *flags=mask?PyBytes_AS_STRING(mask):NULL;
if(flags)memset(flags,0,n);
Py_ssize_t hits=0;
Py_BEGIN_ALLOW_THREADS
/* Finish independent eight-window tiles. A failed level check needs the
rank implementation only for that tile, including a partial tail. */
for(Py_ssize_t lo=0;lo<n;lo+=8){
Py_ssize_t stop=lo+8>n?n:lo+8;
int good=1;
for(Py_ssize_t i=lo;good&&i<stop;i++)for(int h=0;good&&h<c;h++)
good=level_cdf(x+i*t*c+h,(int)t,(int)c,bounds,(int)m,cuts,(int)nq,width,turbo,out+i*m*width*c,h);
if(good){
numeric_eight(x+lo*t*c,bounds,out+lo*m*width*c,tile,t,c,m,width,turbo,(int)(stop-lo));
if(flags)memset(flags+lo,1,stop-lo);
hits+=stop-lo;
}else if(!partial)break;
}
Py_END_ALLOW_THREADS
ok=hits==n;
if(ok || hits==0)Py_CLEAR(mask);
PyMem_Free(cuts);PyMem_Free(tile);
}
#endif
done:
for(int j=0;j<4;++j)if(v[j].obj)PyBuffer_Release(v+j);
if(PyErr_Occurred()){Py_XDECREF(mask);return NULL;}
if(mask)return mask;return PyBool_FromLong(ok);
}