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