lib/sharedbook.c

   1 /********************************************************************
   2  *                                                                  *
   3  * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
   4  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
   5  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
   6  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
   7  *                                                                  *
   8  * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2001             *
   9  * by the XIPHOPHORUS Company http://www.xiph.org/                  *
  10  *                                                                  *
  11  ********************************************************************
  12
  13  function: basic shared codebook operations
  14  last mod: $Id: sharedbook.c,v 1.22 2001/12/21 14:52:36 segher Exp $
  15
  16  ********************************************************************/
  17
  18 #include <stdlib.h>
  19 #include <math.h>
  20 #include <string.h>
  21 #include <ogg/ogg.h>
  22 #include "os.h"
  23 #include "vorbis/codec.h"
  24 #include "codebook.h"
  25 #include "scales.h"
  26
  27 /**** pack/unpack helpers ******************************************/
  28 int _ilog(unsigned int v){
  29   int ret=0;
  30   while(v){
  31     ret++;
  32     v>>=1;
  33   }
  34   return(ret);
  35 }
  36
  37 /* 32 bit float (not IEEE; nonnormalized mantissa +
  38    biased exponent) : neeeeeee eeemmmmm mmmmmmmm mmmmmmmm
  39    Why not IEEE?  It's just not that important here. */
  40
  41 #define VQ_FEXP 10
  42 #define VQ_FMAN 21
  43 #define VQ_FEXP_BIAS 768 /* bias toward values smaller than 1. */
  44
  45 /* doesn't currently guard under/overflow */
  46 long _float32_pack(float val){
  47   int sign=0;
  48   long exp;
  49   long mant;
  50   if(val<0){
  51     sign=0x80000000;
  52     val= -val;
  53   }
  54   exp= floor(log(val)/log(2.f));
  55   mant=rint(ldexp(val,(VQ_FMAN-1)-exp));
  56   exp=(exp+VQ_FEXP_BIAS)<<VQ_FMAN;
  57
  58   return(sign|exp|mant);
  59 }
  60
  61 float _float32_unpack(long val){
  62   double mant=val&0x1fffff;
  63   int    sign=val&0x80000000;
  64   long   exp =(val&0x7fe00000L)>>VQ_FMAN;
  65   if(sign)mant= -mant;
  66   return(ldexp(mant,exp-(VQ_FMAN-1)-VQ_FEXP_BIAS));
  67 }
  68
  69 /* given a list of word lengths, generate a list of codewords.  Works
  70    for length ordered or unordered, always assigns the lowest valued
  71    codewords first.  Extended to handle unused entries (length 0) */
  72 long *_make_words(long *l,long n){
  73   long i,j;
  74   long marker[33];
  75   long *r=_ogg_malloc(n*sizeof(*r));
  76   memset(marker,0,sizeof(marker));
  77
  78   for(i=0;i<n;i++){
  79     long length=l[i];
  80     if(length>0){
  81       long entry=marker[length];
  82
  83       /* when we claim a node for an entry, we also claim the nodes
  84          below it (pruning off the imagined tree that may have dangled
  85          from it) as well as blocking the use of any nodes directly
  86          above for leaves */
  87
  88       /* update ourself */
  89       if(length<32 && (entry>>length)){
  90         /* error condition; the lengths must specify an overpopulated tree */
  91         _ogg_free(r);
  92         return(NULL);
  93       }
  94       r[i]=entry;
  95
  96       /* Look to see if the next shorter marker points to the node
  97          above. if so, update it and repeat.  */
  98       {
  99         for(j=length;j>0;j--){
 100
 101           if(marker[j]&1){
 102             /* have to jump branches */
 103             if(j==1)
 104               marker[1]++;
 105             else
 106               marker[j]=marker[j-1]<<1;
 107             break; /* invariant says next upper marker would already
 108                       have been moved if it was on the same path */
 109           }
 110           marker[j]++;
 111         }
 112       }
 113
 114       /* prune the tree; the implicit invariant says all the longer
 115          markers were dangling from our just-taken node.  Dangle them
 116          from our *new* node. */
 117       for(j=length+1;j<33;j++)
 118         if((marker[j]>>1) == entry){
 119           entry=marker[j];
 120           marker[j]=marker[j-1]<<1;
 121         }else
 122           break;
 123     }
 124   }
 125
 126   /* bitreverse the words because our bitwise packer/unpacker is LSb
 127      endian */
 128   for(i=0;i<n;i++){
 129     long temp=0;
 130     for(j=0;j<l[i];j++){
 131       temp<<=1;
 132       temp|=(r[i]>>j)&1;
 133     }
 134     r[i]=temp;
 135   }
 136
 137   return(r);
 138 }
 139
 140 /* build the decode helper tree from the codewords */
 141 decode_aux *_make_decode_tree(codebook *c){
 142   const static_codebook *s=c->c;
 143   long top=0,i,j,n;
 144   decode_aux *t=_ogg_malloc(sizeof(*t));
 145   long *ptr0=t->ptr0=_ogg_calloc(c->entries*2,sizeof(*ptr0));
 146   long *ptr1=t->ptr1=_ogg_calloc(c->entries*2,sizeof(*ptr1));
 147   long *codelist=_make_words(s->lengthlist,s->entries);
 148
 149   if(codelist==NULL)return(NULL);
 150   t->aux=c->entries*2;
 151
 152   for(i=0;i<c->entries;i++){
 153     if(s->lengthlist[i]>0){
 154       long ptr=0;
 155       for(j=0;j<s->lengthlist[i]-1;j++){
 156         int bit=(codelist[i]>>j)&1;
 157         if(!bit){
 158           if(!ptr0[ptr])
 159             ptr0[ptr]= ++top;
 160           ptr=ptr0[ptr];
 161         }else{
 162           if(!ptr1[ptr])
 163             ptr1[ptr]= ++top;
 164           ptr=ptr1[ptr];
 165         }
 166       }
 167       if(!((codelist[i]>>j)&1))
 168         ptr0[ptr]=-i;
 169       else
 170         ptr1[ptr]=-i;
 171     }
 172   }
 173   _ogg_free(codelist);
 174
 175   t->tabn = _ilog(c->entries)-4; /* this is magic */
 176   if(t->tabn<5)t->tabn=5;
 177   n = 1<<t->tabn;
 178   t->tab = _ogg_malloc(n*sizeof(*t->tab));
 179   t->tabl = _ogg_malloc(n*sizeof(*t->tabl));
 180   for (i = 0; i < n; i++) {
 181     long p = 0;
 182     for (j = 0; j < t->tabn && (p > 0 || j == 0); j++) {
 183       if (i & (1 << j))
 184         p = ptr1[p];
 185       else
 186         p = ptr0[p];
 187     }
 188     /* now j == length, and p == -code */
 189     t->tab[i] = p;
 190     t->tabl[i] = j;
 191   }
 192
 193   return(t);
 194 }
 195
 196 /* there might be a straightforward one-line way to do the below
 197    that's portable and totally safe against roundoff, but I haven't
 198    thought of it.  Therefore, we opt on the side of caution */
 199 long _book_maptype1_quantvals(const static_codebook *b){
 200   long vals=floor(pow((float)b->entries,1.f/b->dim));
 201
 202   /* the above *should* be reliable, but we'll not assume that FP is
 203      ever reliable when bitstream sync is at stake; verify via integer
 204      means that vals really is the greatest value of dim for which
 205      vals^b->bim <= b->entries */
 206   /* treat the above as an initial guess */
 207   while(1){
 208     long acc=1;
 209     long acc1=1;
 210     int i;
 211     for(i=0;i<b->dim;i++){
 212       acc*=vals;
 213       acc1*=vals+1;
 214     }
 215     if(acc<=b->entries && acc1>b->entries){
 216       return(vals);
 217     }else{
 218       if(acc>b->entries){
 219         vals--;
 220       }else{
 221         vals++;
 222       }
 223     }
 224   }
 225 }
 226
 227 /* unpack the quantized list of values for encode/decode ***********/
 228 /* we need to deal with two map types: in map type 1, the values are
 229    generated algorithmically (each column of the vector counts through
 230    the values in the quant vector). in map type 2, all the values came
 231    in in an explicit list.  Both value lists must be unpacked */
 232 float *_book_unquantize(const static_codebook *b){
 233   long j,k;
 234   if(b->maptype==1 || b->maptype==2){
 235     int quantvals;
 236     float mindel=_float32_unpack(b->q_min);
 237     float delta=_float32_unpack(b->q_delta);
 238     float *r=_ogg_calloc(b->entries*b->dim,sizeof(*r));
 239
 240     /* maptype 1 and 2 both use a quantized value vector, but
 241        different sizes */
 242     switch(b->maptype){
 243     case 1:
 244       /* most of the time, entries%dimensions == 0, but we need to be
 245          well defined.  We define that the possible vales at each
 246          scalar is values == entries/dim.  If entries%dim != 0, we'll
 247          have 'too few' values (values*dim<entries), which means that
 248          we'll have 'left over' entries; left over entries use zeroed
 249          values (and are wasted).  So don't generate codebooks like
 250          that */
 251       quantvals=_book_maptype1_quantvals(b);
 252       for(j=0;j<b->entries;j++){
 253         float last=0.f;
 254         int indexdiv=1;
 255         for(k=0;k<b->dim;k++){
 256           int index= (j/indexdiv)%quantvals;
 257           float val=b->quantlist[index];
 258           val=fabs(val)*delta+mindel+last;
 259           if(b->q_sequencep)last=val;
 260           r[j*b->dim+k]=val;
 261           indexdiv*=quantvals;
 262         }
 263       }
 264       break;
 265     case 2:
 266       for(j=0;j<b->entries;j++){
 267         float last=0.f;
 268         for(k=0;k<b->dim;k++){
 269           float val=b->quantlist[j*b->dim+k];
 270           val=fabs(val)*delta+mindel+last;
 271           if(b->q_sequencep)last=val;
 272           r[j*b->dim+k]=val;
 273         }
 274       }
 275       break;
 276     }
 277
 278     return(r);
 279   }
 280   return(NULL);
 281 }
 282
 283 void vorbis_staticbook_clear(static_codebook *b){
 284   if(b->allocedp){
 285     if(b->quantlist)_ogg_free(b->quantlist);
 286     if(b->lengthlist)_ogg_free(b->lengthlist);
 287     if(b->nearest_tree){
 288       _ogg_free(b->nearest_tree->ptr0);
 289       _ogg_free(b->nearest_tree->ptr1);
 290       _ogg_free(b->nearest_tree->p);
 291       _ogg_free(b->nearest_tree->q);
 292       memset(b->nearest_tree,0,sizeof(*b->nearest_tree));
 293       _ogg_free(b->nearest_tree);
 294     }
 295     if(b->thresh_tree){
 296       _ogg_free(b->thresh_tree->quantthresh);
 297       _ogg_free(b->thresh_tree->quantmap);
 298       memset(b->thresh_tree,0,sizeof(*b->thresh_tree));
 299       _ogg_free(b->thresh_tree);
 300     }
 301
 302     memset(b,0,sizeof(*b));
 303   }
 304 }
 305
 306 void vorbis_staticbook_destroy(static_codebook *b){
 307   if(b->allocedp){
 308     vorbis_staticbook_clear(b);
 309     _ogg_free(b);
 310   }
 311 }
 312
 313 void vorbis_book_clear(codebook *b){
 314   /* static book is not cleared; we're likely called on the lookup and
 315      the static codebook belongs to the info struct */
 316   if(b->decode_tree){
 317     _ogg_free(b->decode_tree->tab);
 318     _ogg_free(b->decode_tree->tabl);
 319
 320     _ogg_free(b->decode_tree->ptr0);
 321     _ogg_free(b->decode_tree->ptr1);
 322     memset(b->decode_tree,0,sizeof(*b->decode_tree));
 323     _ogg_free(b->decode_tree);
 324   }
 325   if(b->valuelist)_ogg_free(b->valuelist);
 326   if(b->codelist)_ogg_free(b->codelist);
 327   memset(b,0,sizeof(*b));
 328 }
 329
 330 int vorbis_book_init_encode(codebook *c,const static_codebook *s){
 331   long j,k;
 332   memset(c,0,sizeof(*c));
 333   c->c=s;
 334   c->entries=s->entries;
 335   c->dim=s->dim;
 336   c->codelist=_make_words(s->lengthlist,s->entries);
 337   c->valuelist=_book_unquantize(s);
 338
 339   /* set the 'zero entry' */
 340   c->zeroentry=-1;
 341   if(c->valuelist){
 342     for(j=0;j<s->entries;j++){
 343       int flag=1;
 344       for(k=0;k<s->dim;k++){
 345         if(fabs(c->valuelist[j*s->dim+k])>1e-12f){
 346           flag=0;
 347           break;
 348         }
 349       }
 350       if(flag)
 351         c->zeroentry=j;
 352     }
 353   }
 354
 355   return(0);
 356 }
 357
 358 int vorbis_book_init_decode(codebook *c,const static_codebook *s){
 359   memset(c,0,sizeof(*c));
 360   c->c=s;
 361   c->entries=s->entries;
 362   c->dim=s->dim;
 363   c->valuelist=_book_unquantize(s);
 364   c->decode_tree=_make_decode_tree(c);
 365   if(c->decode_tree==NULL)goto err_out;
 366   return(0);
 367  err_out:
 368   vorbis_book_clear(c);
 369   return(-1);
 370 }
 371
 372 static float _dist(int el,float *ref, float *b,int step){
 373   int i;
 374   float acc=0.f;
 375   for(i=0;i<el;i++){
 376     float val=(ref[i]-b[i*step]);
 377     acc+=val*val;
 378   }
 379   return(acc);
 380 }
 381
 382 int _best(codebook *book, float *a, int step){
 383   encode_aux_nearestmatch *nt=book->c->nearest_tree;
 384   encode_aux_threshmatch *tt=book->c->thresh_tree;
 385   encode_aux_pigeonhole *pt=book->c->pigeon_tree;
 386   int dim=book->dim;
 387   int ptr=0,k,o;
 388   /*int savebest=-1;
 389     float saverr;*/
 390
 391   /* do we have a threshhold encode hint? */
 392   if(tt){
 393     int index=0;
 394     /* find the quant val of each scalar */
 395     for(k=0,o=step*(dim-1);k<dim;k++,o-=step){
 396       int i;
 397       /* linear search the quant list for now; it's small and although
 398          with > ~8 entries, it would be faster to bisect, this would be
 399          a misplaced optimization for now */
 400       for(i=0;i<tt->threshvals-1;i++)
 401         if(a[o]<tt->quantthresh[i])break;
 402
 403       index=(index*tt->quantvals)+tt->quantmap[i];
 404     }
 405     /* regular lattices are easy :-) */
 406     if(book->c->lengthlist[index]>0) /* is this unused?  If so, we'll
 407                                         use a decision tree after all
 408                                         and fall through*/
 409       return(index);
 410   }
 411
 412   /* do we have a pigeonhole encode hint? */
 413   if(pt){
 414     const static_codebook *c=book->c;
 415     int i,besti=-1;
 416     float best=0.f;
 417     int entry=0;
 418
 419     /* dealing with sequentialness is a pain in the ass */
 420     if(c->q_sequencep){
 421       int pv;
 422       long mul=1;
 423       float qlast=0;
 424       for(k=0,o=0;k<dim;k++,o+=step){
 425         pv=(int)((a[o]-qlast-pt->min)/pt->del);
 426         if(pv<0 || pv>=pt->mapentries)break;
 427         entry+=pt->pigeonmap[pv]*mul;
 428         mul*=pt->quantvals;
 429         qlast+=pv*pt->del+pt->min;
 430       }
 431     }else{
 432       for(k=0,o=step*(dim-1);k<dim;k++,o-=step){
 433         int pv=(int)((a[o]-pt->min)/pt->del);
 434         if(pv<0 || pv>=pt->mapentries)break;
 435         entry=entry*pt->quantvals+pt->pigeonmap[pv];
 436       }
 437     }
 438
 439     /* must be within the pigeonholable range; if we quant outside (or
 440        in an entry that we define no list for), brute force it */
 441     if(k==dim && pt->fitlength[entry]){
 442       /* search the abbreviated list */
 443       long *list=pt->fitlist+pt->fitmap[entry];
 444       for(i=0;i<pt->fitlength[entry];i++){
 445         float this=_dist(dim,book->valuelist+list[i]*dim,a,step);
 446         if(besti==-1 || this<best){
 447           best=this;
 448           besti=list[i];
 449         }
 450       }
 451
 452       return(besti);
 453     }
 454   }
 455
 456   if(nt){
 457     /* optimized using the decision tree */
 458     while(1){
 459       float c=0.f;
 460       float *p=book->valuelist+nt->p[ptr];
 461       float *q=book->valuelist+nt->q[ptr];
 462
 463       for(k=0,o=0;k<dim;k++,o+=step)
 464         c+=(p[k]-q[k])*(a[o]-(p[k]+q[k])*.5);
 465
 466       if(c>0.f) /* in A */
 467         ptr= -nt->ptr0[ptr];
 468       else     /* in B */
 469         ptr= -nt->ptr1[ptr];
 470       if(ptr<=0)break;
 471     }
 472     return(-ptr);
 473   }
 474
 475   /* brute force it! */
 476   {
 477     const static_codebook *c=book->c;
 478     int i,besti=-1;
 479     float best=0.f;
 480     float *e=book->valuelist;
 481     for(i=0;i<book->entries;i++){
 482       if(c->lengthlist[i]>0){
 483         float this=_dist(dim,e,a,step);
 484         if(besti==-1 || this<best){
 485           best=this;
 486           besti=i;
 487         }
 488       }
 489       e+=dim;
 490     }
 491
 492     /*if(savebest!=-1 && savebest!=besti){
 493       fprintf(stderr,"brute force/pigeonhole disagreement:\n"
 494               "original:");
 495       for(i=0;i<dim*step;i+=step)fprintf(stderr,"%g,",a[i]);
 496       fprintf(stderr,"\n"
 497               "pigeonhole (entry %d, err %g):",savebest,saverr);
 498       for(i=0;i<dim;i++)fprintf(stderr,"%g,",
 499                                 (book->valuelist+savebest*dim)[i]);
 500       fprintf(stderr,"\n"
 501               "bruteforce (entry %d, err %g):",besti,best);
 502       for(i=0;i<dim;i++)fprintf(stderr,"%g,",
 503                                 (book->valuelist+besti*dim)[i]);
 504       fprintf(stderr,"\n");
 505       }*/
 506     return(besti);
 507   }
 508 }
 509
 510 /* returns the entry number and *modifies a* to the remainder value ********/
 511 int vorbis_book_besterror(codebook *book,float *a,int step,int addmul){
 512   int dim=book->dim,i,o;
 513   int best=_best(book,a,step);
 514   switch(addmul){
 515   case 0:
 516     for(i=0,o=0;i<dim;i++,o+=step)
 517       a[o]-=(book->valuelist+best*dim)[i];
 518     break;
 519   case 1:
 520     for(i=0,o=0;i<dim;i++,o+=step){
 521       float val=(book->valuelist+best*dim)[i];
 522       if(val==0){
 523         a[o]=0;
 524       }else{
 525         a[o]/=val;
 526       }
 527     }
 528     break;
 529   }
 530   return(best);
 531 }
 532
 533 long vorbis_book_codeword(codebook *book,int entry){
 534   return book->codelist[entry];
 535 }
 536
 537 long vorbis_book_codelen(codebook *book,int entry){
 538   return book->c->lengthlist[entry];
 539 }
 540
 541 #ifdef _V_SELFTEST
 542
 543 /* Unit tests of the dequantizer; this stuff will be OK
 544    cross-platform, I simply want to be sure that special mapping cases
 545    actually work properly; a bug could go unnoticed for a while */
 546
 547 #include <stdio.h>
 548
 549 /* cases:
 550
 551    no mapping
 552    full, explicit mapping
 553    algorithmic mapping
 554
 555    nonsequential
 556    sequential
 557 */
 558
 559 static long full_quantlist1[]={0,1,2,3,    4,5,6,7, 8,3,6,1};
 560 static long partial_quantlist1[]={0,7,2};
 561
 562 /* no mapping */
 563 static_codebook test1={
 564   4,16,
 565   NULL,
 566   0,
 567   0,0,0,0,
 568   NULL,
 569   NULL,NULL
 570 };
 571 static float *test1_result=NULL;
 572
 573 /* linear, full mapping, nonsequential */
 574 static_codebook test2={
 575   4,3,
 576   NULL,
 577   2,
 578   -533200896,1611661312,4,0,
 579   full_quantlist1,
 580   NULL,NULL
 581 };
 582 static float test2_result[]={-3,-2,-1,0, 1,2,3,4, 5,0,3,-2};
 583
 584 /* linear, full mapping, sequential */
 585 static_codebook test3={
 586   4,3,
 587   NULL,
 588   2,
 589   -533200896,1611661312,4,1,
 590   full_quantlist1,
 591   NULL,NULL
 592 };
 593 static float test3_result[]={-3,-5,-6,-6, 1,3,6,10, 5,5,8,6};
 594
 595 /* linear, algorithmic mapping, nonsequential */
 596 static_codebook test4={
 597   3,27,
 598   NULL,
 599   1,
 600   -533200896,1611661312,4,0,
 601   partial_quantlist1,
 602   NULL,NULL
 603 };
 604 static float test4_result[]={-3,-3,-3, 4,-3,-3, -1,-3,-3,
 605                               -3, 4,-3, 4, 4,-3, -1, 4,-3,
 606                               -3,-1,-3, 4,-1,-3, -1,-1,-3,
 607                               -3,-3, 4, 4,-3, 4, -1,-3, 4,
 608                               -3, 4, 4, 4, 4, 4, -1, 4, 4,
 609                               -3,-1, 4, 4,-1, 4, -1,-1, 4,
 610                               -3,-3,-1, 4,-3,-1, -1,-3,-1,
 611                               -3, 4,-1, 4, 4,-1, -1, 4,-1,
 612                               -3,-1,-1, 4,-1,-1, -1,-1,-1};
 613
 614 /* linear, algorithmic mapping, sequential */
 615 static_codebook test5={
 616   3,27,
 617   NULL,
 618   1,
 619   -533200896,1611661312,4,1,
 620   partial_quantlist1,
 621   NULL,NULL
 622 };
 623 static float test5_result[]={-3,-6,-9, 4, 1,-2, -1,-4,-7,
 624                               -3, 1,-2, 4, 8, 5, -1, 3, 0,
 625                               -3,-4,-7, 4, 3, 0, -1,-2,-5,
 626                               -3,-6,-2, 4, 1, 5, -1,-4, 0,
 627                               -3, 1, 5, 4, 8,12, -1, 3, 7,
 628                               -3,-4, 0, 4, 3, 7, -1,-2, 2,
 629                               -3,-6,-7, 4, 1, 0, -1,-4,-5,
 630                               -3, 1, 0, 4, 8, 7, -1, 3, 2,
 631                               -3,-4,-5, 4, 3, 2, -1,-2,-3};
 632
 633 void run_test(static_codebook *b,float *comp){
 634   float *out=_book_unquantize(b);
 635   int i;
 636
 637   if(comp){
 638     if(!out){
 639       fprintf(stderr,"_book_unquantize incorrectly returned NULL\n");
 640       exit(1);
 641     }
 642
 643     for(i=0;i<b->entries*b->dim;i++)
 644       if(fabs(out[i]-comp[i])>.0001){
 645         fprintf(stderr,"disagreement in unquantized and reference data:\n"
 646                 "position %d, %g != %g\n",i,out[i],comp[i]);
 647         exit(1);
 648       }
 649
 650   }else{
 651     if(out){
 652       fprintf(stderr,"_book_unquantize returned a value array: \n"
 653               " correct result should have been NULL\n");
 654       exit(1);
 655     }
 656   }
 657 }
 658
 659 int main(){
 660   /* run the nine dequant tests, and compare to the hand-rolled results */
 661   fprintf(stderr,"Dequant test 1... ");
 662   run_test(&test1,test1_result);
 663   fprintf(stderr,"OK\nDequant test 2... ");
 664   run_test(&test2,test2_result);
 665   fprintf(stderr,"OK\nDequant test 3... ");
 666   run_test(&test3,test3_result);
 667   fprintf(stderr,"OK\nDequant test 4... ");
 668   run_test(&test4,test4_result);
 669   fprintf(stderr,"OK\nDequant test 5... ");
 670   run_test(&test5,test5_result);
 671   fprintf(stderr,"OK\n\n");
 672
 673   return(0);
 674 }
 675
 676 #endif