mdw@git.distorted.org.uk Git - adns/blob - src/types.c

   1 /*
   2  * types.c
   3  * - RR-type-specific code, and the machinery to call it
   4  */
   5 /*
   6  *  This file is part of adns, which is Copyright (C) 1997, 1998 Ian Jackson
   7  *
   8  *  This program is free software; you can redistribute it and/or modify
   9  *  it under the terms of the GNU General Public License as published by
  10  *  the Free Software Foundation; either version 2, or (at your option)
  11  *  any later version.
  12  *
  13  *  This program is distributed in the hope that it will be useful,
  14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  *  GNU General Public License for more details.
  17  *
  18  *  You should have received a copy of the GNU General Public License
  19  *  along with this program; if not, write to the Free Software Foundation,
  20  *  Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  21  */
  22
  23 #include <stdlib.h>
  24 #include <string.h>
  25
  26 #include <arpa/inet.h>
  27
  28 #include "internal.h"
  29
  30 #define R_NOMEM           return adns_s_nolocalmem
  31 #define CSP_ADDSTR(s)     if (!adns__vbuf_appendstr(vb,(s))) R_NOMEM; else;
  32
  33 /*
  34  * order of sections:
  35  *
  36  * _textdata, _qstring        (csp)
  37  * _str                       (mf,cs)
  38  * _intstr                    (mf,cs)
  39  * _manyistr                  (mf,cs)
  40  * _txt                       (pa)
  41  * _inaddr                    (pa,dip,di)
  42  * _addr                      (pa,di,csp,cs)
  43  * _domain                    (pap)
  44  * _host_raw                  (pa)
  45  * _hostaddr                  (pap,pa,dip,di,mfp,mf,csp,cs +pap_findaddrs)
  46  * _mx_raw                    (pa,di)
  47  * _mx                        (pa,di)
  48  * _inthostaddr               (mf,cs)
  49  * _flat                      (mf)
  50  *
  51  * within each section:
  52  *    pap_*
  53  *    pa_*
  54  *    dip_*
  55  *    di_*
  56  *    mfp_*
  57  *    mf_*
  58  *    csp_*
  59  *    cs_*
  60  */
  61
  62 /*
  63  * _textdata, _qstring   (csp)
  64  */
  65
  66 static adns_status csp_textdata(vbuf *vb, const char *dp, int len) {
  67   unsigned char ch;
  68   char buf[10];
  69   int cn;
  70
  71   CSP_ADDSTR("\"");
  72   for (cn=0; cn<len; cn++) {
  73     ch= *dp++;
  74     if (ch >= 32 && ch <= 126 && ch != '"' && ch != '\\') {
  75       if (!adns__vbuf_append(vb,&ch,1)) R_NOMEM;
  76     } else {
  77       sprintf(buf,"\\%02x",ch);
  78       CSP_ADDSTR(buf);
  79     }
  80   }
  81   CSP_ADDSTR("\"");
  82
  83   return adns_s_ok;
  84 }
  85
  86 static adns_status csp_qstring(vbuf *vb, const char *dp) {
  87   return csp_textdata(vb, dp, strlen(dp));
  88 }
  89
  90 /*
  91  * _str  (mf,cs)
  92  */
  93
  94 static void mf_str(adns_query qu, void *datap) {
  95   char **rrp= datap;
  96
  97   adns__makefinal_str(qu,rrp);
  98 }
  99
 100 static adns_status cs_str(vbuf *vb, const void *datap) {
 101   const char *const *rrp= datap;
 102
 103   return csp_qstring(vb,*rrp);
 104 }
 105
 106 /*
 107  * _intstr  (mf,cs)
 108  */
 109
 110 static void mf_intstr(adns_query qu, void *datap) {
 111   adns_rr_intstr *rrp= datap;
 112
 113   adns__makefinal_str(qu,&rrp->str);
 114 }
 115
 116 static adns_status cs_intstr(vbuf *vb, const void *datap) {
 117   const adns_rr_intstr *rrp= datap;
 118   char buf[10];
 119
 120   sprintf(buf,"%u ",rrp->i);
 121   CSP_ADDSTR(buf);
 122   return csp_qstring(vb,rrp->str);
 123 }
 124
 125 /*
 126  * _manyistr   (mf,cs)
 127  */
 128
 129 static void mf_manyistr(adns_query qu, void *datap) {
 130   adns_rr_intstr **rrp= datap;
 131   adns_rr_intstr *te, *table;
 132   void *tablev;
 133   int tc;
 134
 135   for (tc=0, te= *rrp; te->i >= 0; te++, tc++);
 136   tablev= *rrp;
 137   adns__makefinal_block(qu,&tablev,sizeof(*te)*(tc+1));
 138   *rrp= table= tablev;
 139   for (te= *rrp; te->i >= 0; te++)
 140     adns__makefinal_str(qu,&te->str);
 141 }
 142
 143 static adns_status cs_manyistr(vbuf *vb, const void *datap) {
 144   const adns_rr_intstr *const *rrp= datap;
 145   const adns_rr_intstr *current;
 146   adns_status st;
 147   int spc;
 148
 149   for (spc=0, current= *rrp; current->i >= 0; current++) {
 150     if (spc) CSP_ADDSTR(" ");
 151     st= csp_textdata(vb,current->str,current->i); if (st) return st;
 152   }
 153   return adns_s_ok;
 154 }
 155
 156 /*
 157  * _txt   (pa)
 158  */
 159
 160 static adns_status pa_txt(const parseinfo *pai, int cbyte, int max, void *datap) {
 161   adns_rr_intstr **rrp= datap, *table, *te;
 162   const byte *dgram= pai->dgram;
 163   int ti, tc, l, startbyte;
 164
 165   startbyte= cbyte;
 166   if (cbyte >= max) return adns_s_invaliddata;
 167   tc= 0;
 168   while (cbyte < max) {
 169     GET_B(cbyte,l);
 170     cbyte+= l;
 171   }
 172   if (cbyte != max) return adns_s_invaliddata;
 173
 174   table= adns__alloc_interim(pai->qu,sizeof(*table)*(tc+1));
 175   if (!table) R_NOMEM;
 176
 177   for (cbyte=startbyte, ti=0, te=table; ti<tc; ti++, te++) {
 178     GET_B(cbyte,l);
 179     te->str= adns__alloc_interim(pai->qu, l+1);
 180     if (!te->str) R_NOMEM;
 181     te->str[l]= 0;
 182     memcpy(te->str,dgram+cbyte,l);
 183     te->i= l;
 184   }
 185   assert(cbyte == max);
 186
 187   te->i= -1;
 188   te->str= 0;
 189
 190   *rrp= table;
 191   return adns_s_ok;
 192 }
 193
 194 /*
 195  * _inaddr   (pa,dip,di)
 196  */
 197
 198 static adns_status pa_inaddr(const parseinfo *pai, int cbyte, int max, void *datap) {
 199   struct in_addr *storeto= datap;
 200
 201   if (max-cbyte != 4) return adns_s_invaliddata;
 202   memcpy(storeto, pai->dgram + cbyte, 4);
 203   return adns_s_ok;
 204 }
 205
 206 static int dip_inaddr(struct in_addr a, struct in_addr b) {
 207   /* fixme implement sortlist */
 208   return 0;
 209 }
 210
 211 static int di_inaddr(const void *datap_a, const void *datap_b) {
 212   const struct in_addr *ap= datap_a, *bp= datap_b;
 213
 214   return dip_inaddr(*ap,*bp);
 215 }
 216
 217 static adns_status cs_inaddr(vbuf *vb, const void *datap) {
 218   const struct in_addr *rrp= datap, rr= *rrp;
 219   const char *ia;
 220
 221   ia= inet_ntoa(rr); assert(ia);
 222   CSP_ADDSTR(ia);
 223   return adns_s_ok;
 224 }
 225
 226 /*
 227  * _addr   (pa,di,csp,cs)
 228  */
 229
 230 static adns_status pa_addr(const parseinfo *pai, int cbyte, int max, void *datap) {
 231   adns_rr_addr *storeto= datap;
 232   const byte *dgram= pai->dgram;
 233
 234   if (max-cbyte != 4) return adns_s_invaliddata;
 235   storeto->len= sizeof(storeto->addr.inet);
 236   memset(&storeto->addr,0,sizeof(storeto->addr.inet));
 237   storeto->addr.inet.sin_family= AF_INET;
 238   storeto->addr.inet.sin_port= 0;
 239   memcpy(&storeto->addr.inet.sin_addr,dgram+cbyte,4);
 240   return adns_s_ok;
 241 }
 242
 243 static int di_addr(const void *datap_a, const void *datap_b) {
 244   const adns_rr_addr *ap= datap_a, *bp= datap_b;
 245
 246   assert(ap->addr.sa.sa_family == AF_INET);
 247   return dip_inaddr(ap->addr.inet.sin_addr,bp->addr.inet.sin_addr);
 248 }
 249
 250 static adns_status csp_addr(vbuf *vb, const adns_rr_addr *rrp) {
 251   const char *ia;
 252   static char buf[30];
 253
 254   switch (rrp->addr.inet.sin_family) {
 255   case AF_INET:
 256     CSP_ADDSTR("AF_INET ");
 257     ia= inet_ntoa(rrp->addr.inet.sin_addr); assert(ia);
 258     CSP_ADDSTR(ia);
 259     break;
 260   default:
 261     sprintf(buf,"AF=%u",rrp->addr.sa.sa_family);
 262     CSP_ADDSTR(buf);
 263     break;
 264   }
 265   return adns_s_ok;
 266 }
 267
 268 static adns_status cs_addr(vbuf *vb, const void *datap) {
 269   const adns_rr_addr *rrp= datap;
 270
 271   return csp_addr(vb,rrp);
 272 }
 273
 274 /*
 275  * _domain  (pap)
 276  */
 277
 278 static adns_status pap_domain(const parseinfo *pai, int *cbyte_io, int max,
 279                               char **domain_r, parsedomain_flags flags) {
 280   adns_status st;
 281   char *dm;
 282
 283   st= adns__parse_domain(pai->qu->ads, pai->serv, pai->qu, &pai->qu->vb, flags,
 284                          pai->dgram,pai->dglen, cbyte_io, max);
 285   if (st) return st;
 286   if (!pai->qu->vb.used) return adns_s_invaliddata;
 287
 288   dm= adns__alloc_interim(pai->qu, pai->qu->vb.used+1);
 289   if (!dm) R_NOMEM;
 290
 291   dm[pai->qu->vb.used]= 0;
 292   memcpy(dm,pai->qu->vb.buf,pai->qu->vb.used);
 293
 294   *domain_r= dm;
 295   return adns_s_ok;
 296 }
 297
 298 /*
 299  * _host_raw   (pa)
 300  */
 301
 302 static adns_status pa_host_raw(const parseinfo *pai, int cbyte, int max, void *datap) {
 303   char **rrp= datap;
 304   adns_status st;
 305
 306   st= pap_domain(pai, &cbyte, max, rrp,
 307                  pai->qu->flags & adns_qf_quoteok_anshost ? pdf_quoteok : 0);
 308   if (st) return st;
 309
 310   if (cbyte != max) return adns_s_invaliddata;
 311   return adns_s_ok;
 312 }
 313
 314 /*
 315  * _hostaddr   (pap,pa,dip,di,mfp,mf,csp,cs +icb_hostaddr, pap_findaddrs)
 316  */
 317
 318 static adns_status pap_findaddrs(const parseinfo *pai, adns_rr_hostaddr *ha,
 319                                  int *cbyte_io, int count, int dmstart) {
 320   int rri, naddrs;
 321   int type, class, rdlen, rdstart, ownermatched;
 322   adns_status st;
 323
 324   for (rri=0, naddrs=-1; rri<count; rri++) {
 325     st= adns__findrr_anychk(pai->qu, pai->serv, pai->dgram, pai->dglen, cbyte_io,
 326                             &type, &class, &rdlen, &rdstart,
 327                             pai->dgram, pai->dglen, dmstart, &ownermatched);
 328     if (st) return st;
 329     if (!ownermatched || class != DNS_CLASS_IN || type != adns_r_a) {
 330       if (naddrs>0) break; else continue;
 331     }
 332     if (naddrs == -1) {
 333       naddrs= 0;
 334     }
 335     if (!adns__vbuf_ensure(&pai->qu->vb, (naddrs+1)*sizeof(adns_rr_addr))) R_NOMEM;
 336     st= pa_addr(pai, rdstart,rdstart+rdlen,
 337                 pai->qu->vb.buf + naddrs*sizeof(adns_rr_addr));
 338     if (st) return st;
 339     naddrs++;
 340   }
 341   if (naddrs >= 0) {
 342     ha->addrs= adns__alloc_interim(pai->qu, naddrs*sizeof(adns_rr_addr));
 343     if (!ha->addrs) R_NOMEM;
 344     memcpy(ha->addrs, pai->qu->vb.buf, naddrs*sizeof(adns_rr_addr));
 345     ha->naddrs= naddrs;
 346     ha->astatus= adns_s_ok;
 347
 348     adns__isort(ha->addrs, naddrs, sizeof(adns_rr_addr), pai->qu->vb.buf, di_addr);
 349   }
 350   return adns_s_ok;
 351 }
 352
 353 static void icb_hostaddr(adns_query parent, adns_query child) {
 354   adns_rr_hostaddr *rrp= child->context.intern.info.hostaddr;
 355   adns_answer *cans= child->answer;
 356
 357   rrp->astatus= cans->status;
 358   rrp->naddrs= cans->nrrs;
 359   rrp->addrs= cans->rrs.addr;
 360   adns__transfer_interim(child, parent, rrp->addrs, rrp->naddrs*sizeof(adns_rr_addr));
 361 }
 362
 363 static adns_status pap_hostaddr(const parseinfo *pai, int *cbyte_io,
 364                                 int max, adns_rr_hostaddr *rrp) {
 365   adns_status st;
 366   int dmstart, cbyte;
 367   qcontext ctx;
 368   int id;
 369   adns_query nqu;
 370
 371   dmstart= cbyte= *cbyte_io;
 372   st= pap_domain(pai, &cbyte, max, &rrp->host,
 373                  pai->qu->flags & adns_qf_quoteok_anshost ? pdf_quoteok : 0);
 374   if (st) return st;
 375   *cbyte_io= cbyte;
 376
 377   rrp->astatus= adns_s_ok;
 378   rrp->naddrs= -1;
 379   rrp->addrs= 0;
 380
 381   cbyte= pai->nsstart;
 382
 383   st= pap_findaddrs(pai, rrp, &cbyte, pai->nscount, dmstart);
 384   if (st) return st;
 385   if (rrp->naddrs != -1) return adns_s_ok;
 386
 387   st= pap_findaddrs(pai, rrp, &cbyte, pai->arcount, dmstart);
 388   if (st) return st;
 389   if (rrp->naddrs != -1) return adns_s_ok;
 390
 391   st= adns__mkquery_frdgram(pai->ads, &pai->qu->vb, &id,
 392                             pai->dgram, pai->dglen, dmstart,
 393                             adns_r_addr, adns_qf_quoteok_query);
 394   if (st) return st;
 395
 396   ctx.intern.callback= icb_hostaddr;
 397   ctx.intern.info.hostaddr= rrp;
 398   st= adns__internal_submit(pai->ads, &nqu, adns__findtype(adns_r_addr),
 399                             &pai->qu->vb, id,
 400                             adns_qf_quoteok_query, pai->now, 0, &ctx);
 401   if (st) return st;
 402
 403   nqu->parent= pai->qu;
 404   LIST_LINK_TAIL_PART(pai->qu->children,nqu,siblings.);
 405
 406   return adns_s_ok;
 407 }
 408
 409 static adns_status pa_hostaddr(const parseinfo *pai, int cbyte, int max, void *datap) {
 410   adns_rr_hostaddr *rrp= datap;
 411   adns_status st;
 412
 413   st= pap_hostaddr(pai, &cbyte, max, rrp);
 414   if (st) return st;
 415   if (cbyte != max) return adns_s_invaliddata;
 416
 417   return adns_s_ok;
 418 }
 419
 420 static int dip_hostaddr(const adns_rr_hostaddr *ap, const adns_rr_hostaddr *bp) {
 421   if (ap->astatus != bp->astatus) return ap->astatus;
 422   if (ap->astatus) return 0;
 423
 424   assert(ap->addrs[0].addr.sa.sa_family == AF_INET);
 425   assert(bp->addrs[0].addr.sa.sa_family == AF_INET);
 426   return dip_inaddr(ap->addrs[0].addr.inet.sin_addr, bp->addrs[0].addr.inet.sin_addr);
 427 }
 428
 429 static int di_hostaddr(const void *datap_a, const void *datap_b) {
 430   const adns_rr_hostaddr *ap= datap_a, *bp= datap_b;
 431
 432   return dip_hostaddr(ap,bp);
 433 }
 434
 435 static void mfp_hostaddr(adns_query qu, adns_rr_hostaddr *rrp) {
 436   void *tablev;
 437
 438   adns__makefinal_str(qu,&rrp->host);
 439   tablev= rrp->addrs;
 440   adns__makefinal_block(qu, &tablev, rrp->naddrs*sizeof(*rrp->addrs));
 441   rrp->addrs= tablev;
 442 }
 443
 444 static void mf_hostaddr(adns_query qu, void *datap) {
 445   adns_rr_hostaddr *rrp= datap;
 446
 447   mfp_hostaddr(qu,rrp);
 448 }
 449
 450 static adns_status csp_hostaddr(vbuf *vb, const adns_rr_hostaddr *rrp) {
 451   const char *to_add;
 452   adns_status st;
 453   int i;
 454
 455   st= csp_qstring(vb,rrp->host); if (st) return st;
 456
 457   if (rrp->astatus) {
 458     CSP_ADDSTR(" - ");
 459     CSP_ADDSTR(adns_strerror(rrp->astatus));
 460   } else {
 461     assert(rrp->naddrs > 0);
 462     for (i=0, to_add= ": "; i<rrp->naddrs; i++, to_add= ", ") {
 463       CSP_ADDSTR(to_add);
 464       st= csp_addr(vb,&rrp->addrs[i]);
 465     }
 466   }
 467   return adns_s_ok;
 468 }
 469
 470 static adns_status cs_hostaddr(vbuf *vb, const void *datap) {
 471   const adns_rr_hostaddr *rrp= datap;
 472
 473   return csp_hostaddr(vb,rrp);
 474 }
 475
 476 /*
 477  * _mx_raw   (pa,di)
 478  */
 479
 480 static adns_status pa_mx_raw(const parseinfo *pai, int cbyte, int max, void *datap) {
 481   const byte *dgram= pai->dgram;
 482   adns_rr_intstr *rrp= datap;
 483   adns_status st;
 484   int pref;
 485
 486   if (cbyte+2 > max) return adns_s_invaliddata;
 487   GET_W(cbyte,pref);
 488   rrp->i= pref;
 489   st= pap_domain(pai, &cbyte, max, &rrp->str,
 490                  pai->qu->flags & adns_qf_quoteok_anshost ? pdf_quoteok : 0);
 491   if (st) return st;
 492
 493   if (cbyte != max) return adns_s_invaliddata;
 494   return adns_s_ok;
 495 }
 496
 497 static int di_mx_raw(const void *datap_a, const void *datap_b) {
 498   const adns_rr_intstr *ap= datap_a, *bp= datap_b;
 499
 500   if (ap->i < bp->i) return 0;
 501   if (ap->i > bp->i) return 1;
 502   return 0;
 503 }
 504
 505 /*
 506  * _mx   (pa,di)
 507  */
 508
 509 static adns_status pa_mx(const parseinfo *pai, int cbyte, int max, void *datap) {
 510   const byte *dgram= pai->dgram;
 511   adns_rr_inthostaddr *rrp= datap;
 512   adns_status st;
 513   int pref;
 514
 515   if (cbyte+2 > max) return adns_s_invaliddata;
 516   GET_W(cbyte,pref);
 517   rrp->i= pref;
 518   st= pap_hostaddr(pai, &cbyte, max, &rrp->ha);
 519   if (st) return st;
 520
 521   if (cbyte != max) return adns_s_invaliddata;
 522   return adns_s_ok;
 523 }
 524
 525 static int di_mx(const void *datap_a, const void *datap_b) {
 526   const adns_rr_inthostaddr *ap= datap_a, *bp= datap_b;
 527
 528   if (ap->i < bp->i) return 0;
 529   if (ap->i > bp->i) return 1;
 530   return dip_hostaddr(&ap->ha,&bp->ha);
 531 }
 532
 533 /*
 534  * _inthostaddr  (mf,cs)
 535  */
 536
 537 static void mf_inthostaddr(adns_query qu, void *datap) {
 538   adns_rr_inthostaddr *rrp= datap;
 539
 540   mfp_hostaddr(qu,&rrp->ha);
 541 }
 542
 543 static adns_status cs_inthostaddr(vbuf *vb, const void *datap) {
 544   const adns_rr_inthostaddr *rrp= datap;
 545   char buf[10];
 546
 547   sprintf(buf,"%u ",rrp->i);
 548   CSP_ADDSTR(buf);
 549
 550   return csp_hostaddr(vb,&rrp->ha);
 551 }
 552
 553 /*
 554  * _flat   (mf)
 555  */
 556
 557 static void mf_flat(adns_query qu, void *data) { }
 558
 559 /*
 560  * Now the table.
 561  */
 562
 563 #define TYPESZ_M(member)           (sizeof(*((adns_answer*)0)->rrs.member))
 564
 565 #define DEEP_MEMB(memb) TYPESZ_M(memb), mf_##memb, cs_##memb
 566 #define FLAT_MEMB(memb) TYPESZ_M(memb), mf_flat, cs_##memb
 567
 568 #define DEEP_TYPE(code,rrt,fmt,memb,parser,comparer) \
 569  { adns_r_##code, rrt, fmt, TYPESZ_M(memb), mf_##memb, cs_##memb, parser, comparer }
 570 #define FLAT_TYPE(code,rrt,fmt,memb,parser,comparer) \
 571  { adns_r_##code, rrt, fmt, TYPESZ_M(memb), mf_flat, cs_##memb, parser, comparer }
 572
 573 static const typeinfo typeinfos[] = {
 574 /* Must be in ascending order of rrtype ! */
 575 /* mem-mgmt code     rrt     fmt      member       parser        comparer    */
 576
 577   FLAT_TYPE(a,       "A",     0,      inaddr,      pa_inaddr,    di_inaddr   ),
 578   DEEP_TYPE(ns_raw,  "NS",   "raw",   str,         pa_host_raw,  0           ),
 579   DEEP_TYPE(cname,   "CNAME", 0,      str,         pa_host_raw,  0           ),
 580 #if 0
 581   DEEP_TYPE(soa_raw, "SOA",  "raw",   soa,         pa_soa,       0           ),
 582 #endif
 583   DEEP_TYPE(ptr_raw, "PTR",  "raw",   str,         pa_host_raw,  0           ),
 584 #if 0
 585   DEEP_TYPE(hinfo,   "HINFO", 0,      strpair,     pa_hinfo,     0           ),
 586 #endif
 587   DEEP_TYPE(mx_raw,  "MX",   "raw",   intstr,      pa_mx_raw,    di_mx_raw   ),
 588   DEEP_TYPE(txt,     "TXT",   0,      manyistr,    pa_txt,       0           ),
 589 #if 0
 590   DEEP_TYPE(rp_raw,  "RP",   "raw",   strpair,     pa_rp,        0           ),
 591 #endif
 592
 593   FLAT_TYPE(addr,    "A",  "addr",    addr,        pa_addr,      di_addr     ),
 594   DEEP_TYPE(ns,      "NS", "+addr",   hostaddr,    pa_hostaddr,  di_hostaddr ),
 595 #if 0
 596   DEEP_TYPE(ptr,     "PTR","checked", str,         pa_ptr,       0           ),
 597 #endif
 598   DEEP_TYPE(mx,      "MX", "+addr",   inthostaddr, pa_mx,        di_mx       ),
 599
 600 #if 0
 601   DEEP_TYPE(soa,     "SOA","822",     soa,         pa_soa,        0          ),
 602   DEEP_TYPE(rp,      "RP", "822",     strpair,     pa_rp,         0          ),
 603 #endif /* fixme - implement all types */
 604 };
 605
 606 const typeinfo *adns__findtype(adns_rrtype type) {
 607   const typeinfo *begin, *end, *mid;
 608
 609   begin= typeinfos;  end= typeinfos+(sizeof(typeinfos)/sizeof(typeinfo));
 610
 611   while (begin < end) {
 612     mid= begin + ((end-begin)>>1);
 613     if (mid->type == type) return mid;
 614     if (type > mid->type) begin= mid+1;
 615     else end= mid;
 616   }
 617   return 0;
 618 }