libcds/src/static_bitsequence/sdarray.cpp

   1
   2 #include <sdarray.h>
   3
   4 #if 0
   5 typedef unsigned int qword;
   6 #define logD 4
   7 #else
   8 typedef unsigned long long qword;
   9 #define logD 5
  10 #endif
  11 #define PBS (sizeof(uint)*8)
  12 #define D (1<<logD)
  13 #define logM 5
  14 #define M (1<<logM)
  15 #define logP 8
  16 #define P (1<<logP)
  17 #define logLL 16                 // size of word
  18 #define LL (1<<logLL)
  19 //#define logLLL 7
  20 #define logLLL 5
  21 //#define LLL 128
  22 //#define LLL 32
  23 #define LLL (1<<logLLL)
  24 //#define logL 10
  25 //#define logL (logLL-3)
  26 #define logL (logLL-1-5)
  27 #define L (1<<logL)
  28
  29 int __blog(int x) {
  30   int l;
  31   l = 0;
  32   while (x>0) {
  33     x>>=1;
  34     l++;
  35   }
  36   return l;
  37 }
  38
  39
  40 int __setbit(uint *B, int i,int x) {
  41   int j,l;
  42   //printf("%u\n",D);
  43   j = i / D;
  44   l = i % D;
  45   if (x==0) B[j] &= (~(1<<(D-1-l)));
  46   else if (x==1) B[j] |= (1<<(D-1-l));
  47   else {
  48     printf("error __setbit x=%d\n",x);
  49     exit(1);
  50   }
  51   return x;
  52 }
  53
  54
  55 int __setbit2(uchar *B, int i,int x) {
  56   int j,l;
  57
  58   j = i / 8;
  59   l = i % 8;
  60   if (x==0) B[j] &= (~(1<<(8-1-l)));
  61   else if (x==1) B[j] |= (1<<(8-1-l));
  62   else {
  63     printf("error __setbit2 x=%d\n",x);
  64     exit(1);
  65   }
  66   return x;
  67 }
  68
  69
  70 int __setbits(uint *B, int i, int d, int x) {
  71   int j;
  72
  73   for (j=0; j<d; j++) {
  74     __setbit(B,i+j,(x>>(d-j-1))&1);
  75   }
  76   return x;
  77 }
  78
  79
  80 int __getbit(uint *B, int i) {
  81   int j,l;
  82
  83   //j = i / D;
  84   //l = i % D;
  85   j = i >> logD;
  86   l = i & (D-1);
  87   return (B[j] >> (D-1-l)) & 1;
  88 }
  89
  90
  91 int __getbit2(uchar *B, int i) {
  92   int j,l;
  93
  94   //j = i / D;
  95   //l = i % D;
  96   j = i >> 3;
  97   l = i & (8-1);
  98   return (B[j] >> (8-1-l)) & 1;
  99 }
 100
 101
 102 #if 1
 103 uint __getbits(uint *B, int i, int d) {
 104   qword x,z;
 105
 106   B += (i >> logD);
 107   i &= (D-1);
 108   if (i+d <= 2*D) {
 109     x = (((qword)B[0]) << D) + B[1];
 110     x <<= i;
 111     x >>= (D*2-1-d);
 112     x >>= 1;
 113   }
 114   else {
 115     x = (((qword)B[0])<<D)+B[1];
 116     z = (x<<D)+B[2];
 117     x <<= i;
 118     x &= (((qword)1L<<D)-1)<<D;
 119     z <<= i;
 120     z >>= D;
 121     x += z;
 122     x >>= (2*D-d);
 123   }
 124
 125   return x;
 126 }
 127 #endif
 128
 129 #if 0
 130 uint __getbits(uint *B, int i, int d) {
 131   uint j,x;
 132
 133   x = 0;
 134   for (j=0; j<d; j++) {
 135     x <<= 1;
 136     x += __getbit(B,i+j);
 137   }
 138   return x;
 139 }
 140 #endif
 141
 142 static const unsigned int _popCount[] = {
 143   0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
 144   1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
 145   1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
 146   2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
 147   1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
 148   2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
 149   2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
 150   3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
 151   1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
 152   2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
 153   2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
 154   3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
 155   2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
 156   3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
 157   3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
 158   4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
 159 };
 160
 161 static unsigned int __selecttbl[8*256];
 162 static int built = 0;
 163
 164 void make___selecttbl(void) {
 165   if(built) return;
 166   built = 1;
 167   int i,x,r;
 168   uint buf[1];
 169
 170   for (x = 0; x < 256; x++) {
 171     __setbits(buf,0,8,x);
 172     for (r=0; r<8; r++) __selecttbl[(r<<8)+x] = -1;
 173     r = 0;
 174     for (i=0; i<8; i++) {
 175       if (__getbit(buf,i)) {
 176         __selecttbl[(r<<8)+x] = i;
 177         r++;
 178       }
 179     }
 180   }
 181 }
 182
 183
 184 unsigned int __popCount(uint x) {
 185   uint r;
 186   #if 0
 187   r = x;
 188   r = r - ((r>>1) & 0x77777777) - ((r>>2) & 0x33333333) - ((r>>3) & 0x11111111);
 189   r = ((r + (r>>4)) & 0x0f0f0f0f) % 0xff;
 190   #elif 1
 191   r = x;
 192   r = ((r & 0xaaaaaaaa)>>1) + (r & 0x55555555);
 193   r = ((r & 0xcccccccc)>>2) + (r & 0x33333333);
 194   //r = ((r & 0xf0f0f0f0)>>4) + (r & 0x0f0f0f0f);
 195   r = ((r>>4) + r) & 0x0f0f0f0f;
 196   //r = ((r & 0xff00ff00)>>8) + (r & 0x00ff00ff);
 197   r = (r>>8) + r;
 198   //r = ((r & 0xffff0000)>>16) + (r & 0x0000ffff);
 199   r = ((r>>16) + r) & 63;
 200   #else
 201   r = _popCount[x & 0xff];
 202   x >>= 8;
 203   r += _popCount[x & 0xff];
 204   x >>= 8;
 205   r += _popCount[x & 0xff];
 206   x >>= 8;
 207   r += _popCount[x & 0xff];
 208   #endif
 209   return r;
 210 }
 211
 212
 213 unsigned int __popCount8(uint x) {
 214   uint r;
 215   #if 1
 216   r = x;
 217   r = ((r & 0xaa)>>1) + (r & 0x55);
 218   r = ((r & 0xcc)>>2) + (r & 0x33);
 219   r = ((r>>4) + r) & 0x0f;
 220   #else
 221   r = _popCount[x & 0xff];
 222   #endif
 223   return r;
 224 }
 225
 226
 227 int selectd2_save(selectd2 * s, FILE * fp) {
 228   uint wr = 0;
 229   wr += fwrite(&s->n,sizeof(uint),1,fp);
 230   wr += fwrite(&s->m,sizeof(uint),1,fp);
 231   wr += fwrite(&s->size,sizeof(uint),1,fp);
 232   wr += fwrite(&s->ss_len,sizeof(uint),1,fp);
 233   wr += fwrite(&s->sl_len,sizeof(uint),1,fp);
 234   wr += fwrite(s->buf,sizeof(uchar),(s->n+7)/8+1,fp);
 235   uint nl = (s->m-1) / L + 1;
 236   wr += fwrite(s->lp,sizeof(uint),nl+1,fp);
 237   wr += fwrite(s->p,sizeof(uint),nl+1,fp);
 238   wr += fwrite(s->ss,sizeof(ushort),s->ss_len,fp);
 239   wr += fwrite(s->sl,sizeof(uint),s->sl_len,fp);
 240   if(wr!=s->sl_len+s->ss_len+2*(nl+1)+(s->n+7)/8+1+5)
 241     return 1;
 242   return 0;
 243 }
 244
 245
 246 int selectd2_load(selectd2 * s, FILE * fp) {
 247   uint rd = 0;
 248   rd += fread(&s->n,sizeof(uint),1,fp);
 249   rd += fread(&s->m,sizeof(uint),1,fp);
 250   rd += fread(&s->size,sizeof(uint),1,fp);
 251   rd += fread(&s->ss_len,sizeof(uint),1,fp);
 252   rd += fread(&s->sl_len,sizeof(uint),1,fp);
 253   s->buf = new uchar[(s->n+7)/8+1];
 254   rd += fread(s->buf,sizeof(uchar),(s->n+7)/8+1,fp);
 255   uint nl = (s->m-1) / L + 1;
 256   s->lp = new uint[nl+1];
 257   rd += fread(s->lp,sizeof(uint),nl+1,fp);
 258   s->p = new uint[nl+1];
 259   rd += fread(s->p,sizeof(uint),nl+1,fp);
 260   s->ss = new ushort[s->ss_len];
 261   rd += fread(s->ss,sizeof(ushort),s->ss_len,fp);
 262   s->sl = new uint[s->sl_len];
 263   rd += fread(s->sl,sizeof(uint),s->sl_len,fp);
 264   if(rd!=s->sl_len+s->ss_len+2*(nl+1)+(s->n+7)/8+1+5)
 265     return 1;
 266   return 0;
 267 }
 268
 269
 270 void selectd2_free(selectd2 * s) {
 271   //delete [] s->buf;
 272   delete [] s->lp;
 273   delete [] s->p;
 274   delete [] s->ss;
 275   delete [] s->sl;
 276 }
 277
 278
 279 int selectd2_construct(selectd2 *select, int n, uchar *buf) {
 280   int i,m;
 281   int nl;
 282   int p,pp;
 283   int il,is,ml,ms;
 284   int r;
 285   uint *s;
 286
 287   make___selecttbl();
 288
 289   if (L/LLL == 0) {
 290     printf("ERROR: L=%d LLL=%d\n",L,LLL);
 291     exit(1);
 292   }
 293
 294   m = 0;
 295   for (i=0; i<n; i++) m += __getbit2(buf,i);
 296   select->n = n;
 297   select->m = m;
 298   //printf("n=%d m=%d\n",n,m);
 299
 300   select->buf = buf;
 301
 302   s = new uint[m];
 303   m = 0;
 304   for (i=0; i<n; i++) {
 305     if (__getbit2(buf,i)) {
 306       m++;
 307       s[m-1] = i;
 308     }
 309   }
 310
 311   nl = (m-1) / L + 1;
 312   select->size = 0;              //ignoring buf, shared with selects3
 313   select->lp = new uint[nl+1];
 314   for(int k=0;k<nl+1;k++) select->lp[k]=0;
 315   select->size += (nl+1)*sizeof(uint);
 316   select->p = new uint[nl+1];
 317   for(int k=0;k<nl+1;k++) select->p[k]=0;
 318   select->size += (nl+1)*sizeof(uint);
 319
 320   for (r = 0; r < 2; r++) {
 321     ml = ms = 0;
 322     for (il = 0; il < nl; il++) {
 323       pp = s[il*L];
 324       select->lp[il] = pp;
 325       i = min((il+1)*L-1,m-1);
 326       p = s[i];
 327       //printf("%d ",p-pp);
 328       if (p - pp >= LL) {
 329         if (r == 1) {
 330           for (is = 0; is < L; is++) {
 331             if (il*L+is >= m) break;
 332             select->sl[ml*L+is] = s[il*L+is];
 333           }
 334         }
 335         select->p[il] = -((ml<<logL)+1);
 336         ml++;
 337       }
 338       else {
 339         if (r == 1) {
 340           for (is = 0; is < L/LLL; is++) {
 341             if (il*L+is*LLL >= m) break;
 342             select->ss[ms*(L/LLL)+is] = s[il*L+is*LLL] - pp;
 343           }
 344         }
 345         select->p[il] = ms << (logL-logLLL);
 346         ms++;
 347       }
 348     }
 349     if (r == 0) {
 350       select->sl = new uint[ml*L+1];
 351       for(int k=0;k<ml*L+1;k++) select->sl[k]=0;
 352       select->size += sizeof(uint)*(ml*L+1);
 353       select->sl_len = ml*L+1;
 354       select->ss = new ushort[ms*(L/LLL)+1];
 355       for(int k=0;k<ms*(L/LLL)+1;k++) select->ss[k]=0;
 356       select->ss_len = ms*(L/LLL)+1;
 357       select->size += sizeof(ushort)*(ms*(L/LLL)+1);
 358     }
 359   }
 360   delete [] s;
 361   return 0;
 362 }
 363
 364
 365 int selectd2_select(selectd2 *select, int i,int f) {
 366   int p,r;
 367   int il;
 368   int rr;
 369   uchar *q;
 370
 371   if (i == 0) return -1;
 372
 373   #if 0
 374   if (i > select->m) {
 375     printf("ERROR: m=%d i=%d\n",select->m,i);
 376     exit(1);
 377   }
 378   #endif
 379
 380   i--;
 381
 382   il = select->p[i>>logL];
 383   if (il < 0) {
 384     il = -il-1;
 385     //p = select->sl[(il<<logL)+(i & (L-1))];
 386     p = select->sl[il+(i & (L-1))];
 387   }
 388   else {
 389     p = select->lp[i>>logL];
 390     //p += select->ss[(il<<(logL-logLLL))+(i & (L-1))/LLL];
 391     p += select->ss[il+((i & (L-1))>>logLLL)];
 392     r = i - (i & (LLL-1));
 393
 394     q = &(select->buf[p>>3]);
 395
 396     if (f == 1) {
 397       rr = p & (8-1);
 398       r -= _popCount[*q >> (8-1-rr)];
 399       //p = p - rr;
 400
 401       while (1) {
 402         rr = _popCount[*q];
 403         if (r + rr >= i) break;
 404         r += rr;
 405         //p += 8;
 406         q++;
 407       }
 408       p = (q - select->buf) << 3;
 409       p += __selecttbl[((i-r-1)<<8)+(*q)];
 410     }
 411     else {
 412       rr = p & (8-1);
 413       r -= _popCount[(*q ^ 0xff) >> (8-1-rr)];
 414       //p = p - rr;
 415
 416       while (1) {
 417         rr = _popCount[*q ^ 0xff];
 418         if (r + rr >= i) break;
 419         r += rr;
 420         //p += 8;
 421         q++;
 422       }
 423       p = (q - select->buf) << 3;
 424       p += __selecttbl[((i-r-1)<<8)+(*q ^ 0xff)];
 425     }
 426   }
 427   return p;
 428 }
 429
 430
 431 int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
 432   int p,r,p2;
 433   int il;
 434   int rr;
 435   uchar *q;
 436
 437   if (i == 0) {
 438     *st = -1;
 439     return -1;
 440   }
 441
 442   #if 0
 443   if (i > select->m) {
 444     printf("ERROR: m=%d i=%d\n",select->m,i);
 445     exit(1);
 446   }
 447   #endif
 448
 449   i--;
 450
 451   il = select->p[i>>logL];
 452   if (il < 0) {
 453     il = -il-1;
 454     //p = select->sl[(il<<logL)+(i & (L-1))];
 455     p = select->sl[il+(i & (L-1))];
 456
 457     if ((i>>logL) == ((i+1)>>logL)) {
 458       p2 = select->sl[il+((i+1) & (L-1))];
 459     }
 460     else {
 461       p2 = selectd2_select(select,i+2,f);
 462     }
 463   }
 464   else {
 465     p = select->lp[i>>logL];
 466     //p += select->ss[(il<<(logL-logLLL))+(i & (L-1))/LLL];
 467     p += select->ss[il+((i & (L-1))>>logLLL)];
 468     r = i - (i & (LLL-1));
 469
 470     q = &(select->buf[p>>3]);
 471
 472     if (f == 1) {
 473       rr = p & (8-1);
 474       r -= _popCount[*q >> (8-1-rr)];
 475       //p = p - rr;
 476
 477       while (1) {
 478         rr = _popCount[*q];
 479         if (r + rr >= i) break;
 480         r += rr;
 481         //p += 8;
 482         q++;
 483       }
 484       p = (q - select->buf) << 3;
 485       p += __selecttbl[((i-r-1)<<8)+(*q)];
 486
 487       if ((i>>logL) == ((i+1)>>logL)) {
 488         i++;
 489         while (1) {
 490           rr = _popCount[*q];
 491           if (r + rr >= i) break;
 492           r += rr;
 493           q++;
 494         }
 495         p2 = (q - select->buf) << 3;
 496         p2 += __selecttbl[((i-r-1)<<8)+(*q)];
 497       }
 498       else {
 499         p2 = selectd2_select(select,i+2,f);
 500       }
 501
 502     }
 503     else {
 504       rr = p & (8-1);
 505       r -= _popCount[(*q ^ 0xff) >> (8-1-rr)];
 506       //p = p - rr;
 507
 508       while (1) {
 509         rr = _popCount[*q ^ 0xff];
 510         if (r + rr >= i) break;
 511         r += rr;
 512         //p += 8;
 513         q++;
 514       }
 515       p = (q - select->buf) << 3;
 516       p += __selecttbl[((i-r-1)<<8)+(*q ^ 0xff)];
 517
 518       if ((i>>logL) == ((i+1)>>logL)) {
 519         i++;
 520         while (1) {
 521           rr = _popCount[*q ^ 0xff];
 522           if (r + rr >= i) break;
 523           r += rr;
 524           q++;
 525         }
 526         p2 = (q - select->buf) << 3;
 527         p2 += __selecttbl[((i-r-1)<<8)+(*q ^ 0xff)];
 528       }
 529       else {
 530         p2 = selectd2_select(select,i+2,f);
 531       }
 532     }
 533   }
 534   *st = p;
 535   *en = p2;
 536   return p;
 537 }
 538
 539
 540 int selects3_save(selects3 * s, FILE * fp) {
 541   uint wr = 0;
 542   wr += fwrite(&s->n,sizeof(uint),1,fp);
 543   wr += fwrite(&s->m,sizeof(uint),1,fp);
 544   wr += fwrite(&s->size,sizeof(uint),1,fp);
 545   wr += fwrite(&s->d,sizeof(uint),1,fp);
 546   wr += fwrite(&s->hi_len,sizeof(uint),1,fp);
 547   wr += fwrite(&s->low_len,sizeof(uint),1,fp);
 548   wr += fwrite(s->hi,sizeof(uchar),s->hi_len,fp);
 549   wr += fwrite(s->low,sizeof(uint),s->low_len,fp);
 550   if(wr!=(6+s->hi_len+s->low_len))
 551     return 1;
 552   if(selectd2_save(s->sd0,fp)) return 2;
 553   if(selectd2_save(s->sd1,fp)) return 3;
 554   return 0;
 555 }
 556
 557
 558 int selects3_load(selects3 * s, FILE * fp) {
 559   uint rd = 0;
 560   rd += fread(&s->n,sizeof(uint),1,fp);
 561   rd += fread(&s->m,sizeof(uint),1,fp);
 562   rd += fread(&s->size,sizeof(uint),1,fp);
 563   rd += fread(&s->d,sizeof(uint),1,fp);
 564   rd += fread(&s->hi_len,sizeof(uint),1,fp);
 565   rd += fread(&s->low_len,sizeof(uint),1,fp);
 566   s->hi = new uchar[s->hi_len];
 567   rd += fread(s->hi,sizeof(uchar),s->hi_len,fp);
 568   s->low = new uint[s->low_len];
 569   rd += fread(s->low,sizeof(uint),s->low_len,fp);
 570   if(rd!=(6+s->hi_len+s->low_len))
 571     return 1;
 572   s->sd0 = new selectd2;
 573   if(selectd2_load(s->sd0,fp)) return 2;
 574   s->sd1 = new selectd2;
 575   if(selectd2_load(s->sd1,fp)) return 3;
 576   delete [] s->sd0->buf;
 577   delete [] s->sd1->buf;
 578   s->sd0->buf = s->hi;
 579   s->sd1->buf = s->hi;
 580   return 0;
 581 }
 582
 583
 584 void selects3_free(selects3 * s) {
 585   delete [] s->hi;
 586   delete [] s->low;
 587   //delete [] s->sd0->buf;
 588   selectd2_free(s->sd0);
 589   delete s->sd0;
 590   selectd2_free(s->sd1);
 591   delete s->sd1;
 592 }
 593
 594
 595 int selects3_construct(selects3 *select, int n, uint *buf) {
 596   int i,m;
 597   int d,mm;
 598   uint *low;
 599   uchar *buf2;
 600   selectd2 *sd0,*sd1;
 601
 602   m = 0;
 603   for (i=0; i<n; i++) m += __getbit(buf,i);
 604   select->n = n;
 605   select->m = m;
 606
 607   if (m == 0) return 0;
 608
 609   mm = m;
 610   d = 0;
 611   while (mm < n) {
 612     mm <<= 1;
 613     d++;
 614   }
 615
 616   select->d = d;
 617
 618   buf2 = new uchar[(2*m+8-1)/8+1];
 619   for(int k=0;k<(2*m+8-1)/8+1;k++) buf2[k]=0;
 620   select->hi_len = (2*m+8-1)/8+1;
 621   low = new uint[(d*m+PBS-1)/PBS+1];
 622   for(uint k=0;k<(d*m+PBS-1)/PBS+1;k++) low[k]=0;
 623   select->low_len = (d*m+PBS-1)/PBS+1;
 624
 625   select->hi = buf2;
 626   select->low = low;
 627   select->size = sizeof(uchar)*((2*m+8-1)/8+1) + sizeof(uint)*((d*m+PBS-1)/PBS+1);
 628
 629   for (i=0; i<m*2; i++) __setbit2(buf2,i,0);
 630
 631   m = 0;
 632   for (i=0; i<n; i++) {
 633     if (__getbit(buf,i)) {
 634       __setbit2(buf2,(i>>d)+m,1);
 635       __setbits(low,m*d,d,i & ((1<<d)-1));
 636       m++;
 637     }
 638   }
 639
 640   sd1 = new selectd2;
 641   sd0 = new selectd2;
 642   select->size += 2*sizeof(selectd2);
 643
 644   selectd2_construct(sd1,m*2,buf2);
 645   select->sd1 = sd1;
 646
 647   for (i=0; i<m*2; i++) __setbit2(buf2,i,1-__getbit2(buf2,i));
 648   selectd2_construct(sd0,m*2,buf2);
 649   select->sd0 = sd0;
 650
 651   for (i=0; i<m*2; i++) __setbit2(buf2,i,1-__getbit2(buf2,i));
 652   return 0;
 653 }
 654
 655 //selects3 * lasts3=NULL;
 656 //int lasti=0;
 657 //int lasts=0;
 658
 659 int selects3_select(selects3 *select, int i) {
 660   int d,x;
 661
 662   #if 0
 663   if (i > select->m) {
 664     printf("ERROR: m=%d i=%d\n",select->m,i);
 665     exit(1);
 666   }
 667   #endif
 668
 669   if (i == 0) return -1;
 670
 671   d = select->d;
 672         /*if(select->lasti==(uint)i-1) {
 673                 while(!__getbit2(select->sd1->buf,++select->lasts));
 674         }
 675         else {
 676           select->lasts = selectd2_select(select->sd1,i,1);
 677         }
 678         select->lasti = i;
 679         //lasts3 = select; */
 680         x = selectd2_select(select->sd1,i,1) - (i-1);
 681   //x = (select->lasts-(i-1)) << d;
 682   x <<= d;
 683   x += __getbits(select->low,(i-1)*d,d);
 684   return x;
 685 }
 686
 687
 688 int selects3_selectnext(selects3 *select, int i) {
 689         //return selects3_select(select,selects3_rank(select,i)+1);
 690   int d,x,w,y;
 691   int r,j;
 692   int z,ii;
 693   uint *q;
 694   d = select->d;
 695   q = select->low;
 696   ii = i>>d;
 697   y = selectd2_select(select->sd0,ii,0)+1;
 698         int k2=y-ii;
 699   x = y - ii;
 700         int x_orig = x;
 701   j = i - (ii<<d);
 702   r = y & 7;
 703   y >>= 3;
 704   z = select->hi[y];
 705   while (1) {
 706     if (((z << r) & 0x80) == 0) {
 707                         if(x!=x_orig) k2++;
 708                         break;
 709                 }
 710     w = __getbits(q,x*d,d);
 711     if (w >= j) {
 712       if (w == j) {
 713                                 if(__getbit2(select->hi,(8*y+r))) k2++;
 714                                 x++;
 715                                 r++;
 716                         }
 717       break;
 718     }
 719     x++;
 720     r++;
 721                 if(__getbit2(select->hi,(8*y+r))) k2++;
 722     if (r == 8) {
 723       r = 0;
 724       y++;
 725       z = select->hi[y];
 726     }
 727   }
 728         if(x==select->m)
 729                 return (uint)-1;
 730         int c=8*y+r;
 731         int fin=0;
 732         for(int kk=0;kk<8-r;kk++) {
 733                 if(__getbit2(select->hi,c)) {
 734                         fin=1;
 735                         break;
 736                 }
 737                 c++;
 738         }
 739         if(!fin) {
 740                 int pp = c/8;
 741                 while(select->hi[pp]==0) {
 742                         pp++;
 743                         c+=8;
 744                 }
 745                 while(!__getbit2(select->hi,c)) c++;
 746         }
 747         c -= (k2);
 748   return __getbits(q,x*d,d)+((c)<<d);
 749 }
 750
 751 int selects3_rank(selects3 *select, int i) {
 752   int d,x,w,y;
 753   int r,j;
 754   int z,ii;
 755   uint *q;
 756
 757   d = select->d;
 758   q = select->low;
 759
 760   ii = i>>d;
 761
 762   y = selectd2_select(select->sd0,ii,0)+1;
 763   //  selectd2_select2(select->sd0,ii,0,&y1,&y2);
 764   //y1++;  y2++;
 765   //printf("y %d y1 %d  %d\n",y,y1,y2-y1);
 766
 767   x = y - ii;
 768
 769   j = i - (ii<<d);
 770
 771   r = y & 7;
 772   y >>= 3;
 773   z = select->hi[y];
 774   while (1) {
 775     if (((z << r) & 0x80) == 0) break;
 776     w = __getbits(q,x*d,d);
 777     if (w >= j) {
 778       if (w == j) x++;
 779       break;
 780     }
 781     x++;
 782     r++;
 783     if (r == 8) {
 784       r = 0;
 785       y++;
 786       z = select->hi[y];
 787     }
 788   }
 789
 790         return x;
 791 }
 792